Problem Statement

Chokinbako lives in Country A. In this country, the unit of currency is called the yen, and $N$ kinds of coins are used: $A_1$-yen coins, $A_2$-yen coins, …, $A_N$-yen coins.

Chokinbako has saved up coins and has $10^{100}$ of every coin. One day, Yukiusagi appeared and said that she wanted to deposit $M$ yen. Yukiusagi currently has $K_1$ $A_1$-yen coins, $K_2$ $A_2$-yen coins, …, $K_N$ $A_N$-yen coins. Chokinbako wants to minimize the number of coins Yukiusagi will have after the deposit. To this end, Chokinbako decided to have Yukiusagi deposit more than needed at first and then return the change. Precisely, a non-negative integer $x$ is chosen, Yukiusagi first pays Chokinbako exactly $M + x$ yen in coins, and then Chokinbako pays Yukiusagi exactly $x$ yen in coins.

Write a program to find the minimum number of coins Yukiusagi will have after the deposit. However, if it is impossible to deposit exactly $M$ yen, point this out.

Input

$N$ $M$
$A_1$ $A_2$ $\cdots$ $A_N$
$K_1$ $K_2$ $\cdots$ $K_N$

• All input values are integers.
• $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$).

Output

Output on $1$ line the minimum number of coins Yukiusagi will have after the deposit. However, if it is impossible to deposit exactly $M$ yen, output $-1$ instead.

Sample

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