問題文

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

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

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

制約

• $1 \le N \le 18$
• $1 \le W \le 10^9$
• $1 \le w_i \le W$
• 入力はすべて整数である

入力

出力

答えを $1$ 行に出力せよ。

入出力例

4 5
1 2 3 4

2

$\{1, 4\}, \{2, 3\}$ と分けてアイテムボックスに入れることで最小の $2$ 個を達成できます。