問題
私はスーパーマーケットで、レジのアルバイトをして生計を建てている。最近、レジのボタンを強く叩きすぎていたのか分からないけど、挙動がおかしくなってしまった。
お客さんがお金を払うと、当然お釣りを払わないといけない。当然、お釣りの金額を指定して、お釣りを払おうとするのだが、このレジのお釣り口がおかしくて、異なる種類の硬貨は複数枚出てくるのだが、同じ種類の硬貨は同時に 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