Coin Purse Design

2 secs 1024 MB
ocv_contest's icon ocv_contest

問題文

A 君は硬貨入れの設計をしようとしています。
A 君は手荷物を小さくしたいためなるべく小さい硬貨入れが欲しいですが、同時に心配性でもあるので、硬貨入れに硬貨が入りきらないということがないようにしたいです。

A 君が住む国には 11 種類の紙幣と NN 種類の硬貨があり、紙幣の金額は BB 、硬貨の金額はそれぞれ A1,A2,,ANA_1, A_2, \dots , A_N です。
NN 種類の硬貨は全て形・大きさが同じであるとします。

A 君は硬貨入れの大きさ、つまり硬貨入れに入る硬貨の枚数が十分かを知るため、以下のようなシミュレーションを考えました。

シミュレーション

  1. 最初、紙幣を 1010010^{100} 枚、硬貨を 00 枚持っている。
  2. 以下の処理(以降「支払い処理」と呼ぶ)を 1010010^{100} 回繰り返す。
    1. 11 以上 BB 未満の整数 xx をランダムに選ぶ。
    2. 金額 xx を支払う。このとき、 お釣りを受け取ったあとの手持ちの硬貨の枚数が最小になるように支払いを行う
      • ただし、お釣りは必ず硬貨の枚数が最小なパターンで返ってくるものとする(枚数が最小なパターンが複数ある場合、それらのいずれかがランダムに選ばれる)。
    3. お釣りを受け取ったあとの手持ちの硬貨の枚数が硬貨入れの容量を超えた場合、硬貨入れの容量は十分でないとしてシミュレーションを終了する。
  3. 手持ちの硬貨の枚数が硬貨入れの容量を超えずに 1010010^{100} 回の「支払い処理」を終えた場合、硬貨入れの容量は十分であるとしてシミュレーションを終了する。

しかし、このシミュレーションは膨大な時間がかかってしまいます。
よって、このシミュレーションを行う代わりに、このシミュレーションで必ず硬貨入れの容量が十分であるとされるような硬貨入れの容量(硬貨入れに入る硬貨の枚数)の最小値を求めてください。

制約

  • 1N201 \le N \le 20
  • B100,000B \le 100{,}000
  • 1=A1<A2<<AN<B1 = A_1 \lt A_2 \lt \dots \lt A_{N} \lt B
  • 入力は全て整数

入力

入力は以下の形式で与えられます。

NN BB
A1A_1 A2A_2 \ldots ANA_N

出力

条件を満たす硬貨入れの容量の最小値を出力せよ。

入出力例

入力例 1

6 1000
1 5 10 50 100 500

出力例 1

15

入力例 2

3 9
1 4 5

出力例 2

3

Submit


Go (1.21)