007 - レジが壊れた

時間制限 1 秒 / メモリ制限 128 MB / 得点 400 / x 0 /


TLE
1sec
MLE
128MB
得点
400

問題

私はスーパーマーケットで、レジのアルバイトをして生計を建てている。最近、レジのボタンを強く叩きすぎていたのか分からないけど、挙動がおかしくなってしまった。

お客さんがお金を払うと、当然お釣りを払わないといけない。当然、お釣りの金額を指定して、お釣りを払おうとするのだが、このレジのお釣り口がおかしくて、異なる種類の硬貨は複数枚出てくるのだが、同じ種類の硬貨は同時に 1 枚しか出ない。もう一度同じ種類の硬貨を出すには、また新たにお釣りの金額を指定しなければならない。

店長にレジが壊れたことがバレると大変だ。生活が危ない。そこで、最小のお釣りの金額の指定回数を求めて欲しい。

また、私の住む国では N 種類の硬貨が存在する。お釣りの金額は、それぞれの硬貨ごとに枚数を個別で指定できるものとする。

入力

N M
A1 A2 ... AN

1 行目に、硬貨の種類数 N と、お釣りの金額 M が与えられる。
2 行目には、それぞれの硬貨の金額 Ai (1 ≦ i < N) が与えられる。

制約

  • 1 ≦ N ≦ 10
  • 1 ≦ M ≦ 105
  • 1 ≦ Ai ≦ 105
  • 与えられた硬貨を用いて、お釣り M を支払えることが保証される

出力

1行に、最小のお釣りの金額の指定回数を出力せよ。

入出力例

入力例1

6 330
1 5 10 50 100 500

出力例1

2

入力例2

7 127
1 2 4 8 16 32 64

出力例2

1

入力例3

2 10000
1000 2000

出力例3

4