「お菓子の詰め合わせ」を解くために：part 2 D(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
A 君は遠足に持っていくお菓子を買います。
売っているお菓子は N 種類あり、i 番目のお菓子の値段は x_i 円です。
A 君が使えるお金は X 円で、合計金額が X 円を超えないように買わなければなりません。
同じお菓子を複数買うことはできません。
お釣りの最小化は考えず、合計金額が X 円以内となるように買うときに、
買えるお菓子の種類数（個数）を最大にしたときの最大個数を求めてください。
なお、少なくとも 1 種類は X 円以内で買えるものが存在します。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N X
x_1
x_2
...
x_N
* 1 行目に、選択できるお菓子の種類数と、使える金額を表す整数 N, X がこの順で半角スペース区切りで与えられます。
* 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には、i 番目のお菓子の値段を表す整数 x_i が与えられます。
* 入力は合計で N + 1 行となり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
合計金額が X 円以内となるように買えるお菓子の種類数（個数）の最大値を整数で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
* 1 ≦ N ≦ 20
* 0 < X ≦ 5000
* 0 < x_i < 5000 (1 ≦ i ≦ N)
* x_i ≦ X を満たす i が少なくとも 1 つ存在する
- 入力例1
-
4 3
4
5
5
5
- 出力例1
-
0
- 入力例2
-
3 5
5
5
5
- 出力例2
-
1
