Postage stamps

Input

The first line contains two integers $n$ and $k$ (1 \leq n \leq 32, 1 \leq k \leq 10^9), separated by a space.

The second line contains $n$ integers p_1, p_2, \dotsc, p_n (p_i is the cost of the $i$-th stamp).

The third line contains $n$ integers h_1, h_2, \dotsc, h_n, where h_i = 1 if you already own the $i$-th stamp, and $0$ otherwise.

The fourth line contains $n$ integers v_1, v_2, \dotsc, v_n (v_i is the collection value of the $i$-th stamp).

Output

Output a single integer — the minimum amount of money you must spend to obtain a collection of stamps from this series with a total collection value of at least $k$.

If it is possible to achieve this value without spending any additional money, or even by making a profit from transactions, output $0$.

If it is impossible to achieve the desired collection value with any additional investment, output $-1$.

Esempi