問題文

貯金箱さんは 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$ を出力してください．

サンプル

6 31
1 5 10 50 100 500
1 1 0 1 1 1

5

2 1
47 53
1 1

-1

3 6
1 3 4
2 2 1

2