1D Bin Packing

2 secs 1024 MB
magurofly

問題文


個のアイテムがあり、 番目のアイテムの重量は です。

重量の合計が になるまでいくらでも物体が入るアイテムボックスがあります。

これらのアイテムのいずれもアイテムボックスに入っているようにするには、アイテムボックスは最小で何個必要ですか?

制約


  • 入力はすべて整数である

入力


出力


答えを 行に出力せよ。

入出力例


入力例1
4 5
1 2 3 4
出力例1
2

と分けてアイテムボックスに入れることで最小の 個を達成できます。

Submit


Go (1.14)