問題一覧 > 通常問題

No.288 貯金箱の仕事

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : 👑 hos.lyrichos.lyric
8 ProblemId : 333 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:02

問題文

貯金箱さんは A 国に住んでいます.この国では通貨の単位は円と呼ばれ,$A_1$ 円玉,$A_2$ 円玉,…,$A_N$ 円玉の,$N$ 種類の硬貨が使われています.

貯金箱さんは硬貨を貯めに貯めて,どの硬貨も $10^{100}$ 枚持っています.あるとき,ゆきうさぎさんが現れ,$M$ 円の貯金をしたいと言いました.ゆきうさぎさんは,今,$A_1$ 円玉を $K_1$ 枚,$A_2$ 円玉を $K_2$ 枚,…,$A_N$ 円玉を $K_N$ 枚持っています.貯金箱さんは,貯金後にゆきうさぎさんが持っていることになる硬貨の枚数を最小にしてあげようと思いました.このために,ゆきうさぎさんに一旦多めに貯金してもらってからお釣りを返すという方法をとることにしました.正確には,非負整数 $x$ を選び,まずゆきうさぎさんが貯金箱さんに $M + x$ 円を硬貨でちょうど支払ってから,貯金箱さんがゆきうさぎさんに $x$ 円を硬貨でちょうど支払います.

貯金後にゆきうさぎさんの持っていることになる硬貨の枚数の最小値をプログラムを求めてください.ただし,ちょうど $M$ 円を貯金することが不可能ならば,それを指摘してください.

入力

$N$ $M$
$A_1$ $A_2$ $\cdots$ $A_N$
$K_1$ $K_2$ $\cdots$ $K_N$
  • 入力の値はすべて整数.
  • $1 \le N \le 500$.
  • $1 \le M \le 10^{18}$.
  • $1 \le A_1 \lt A_2 \lt \cdots \lt A_N \le 500$.
  • $0 \le K_i \le 10^{12}$ ($i = 1, 2, \ldots, N$).

出力

貯金後にゆきうさぎさんの持っていることになる硬貨の枚数の最小値を $1$ 行に出力してください.ただし,ちょうど $M$ 円を貯金することが不可能ならば,代わりに $-1$ を出力してください.

サンプル

サンプル1
入力
6 31
1 5 10 50 100 500
1 1 0 1 1 1
出力
5

例えば,$50$ 円玉 $1$ 枚を支払って $19$ 円のお釣りを受け取るより,$1$ 円玉 $1$ 枚 と $50$ 円玉 $1$ 枚を支払って $10$ 円玉 $2$ 枚のお釣りを受け取ったほうが,硬貨が少なくなります.

サンプル2
入力
2 1
47 53
1 1
出力
-1

この例では,ちょうど $1$ 円を貯金することはできません.

サンプル3
入力
3 6
1 3 4
2 2 1
出力
2

例えば,$1$ 円玉 $2$ 枚と $4$ 円玉 $1$ 枚で $6$ 円を支払い,お釣りを $0$ 円にしてもかまいません.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。