Mixed Spice１

When cooking, using a mix of spices enhances the flavor more than using only one type of spice. Mixed spice is a seasoning made by mixing several spices in a predetermined ratio.

You are trying to make as large a quantity of mixed spices as possible by purchasing a couple of different spices as your budget allows. You already have some of the spices on hand. In addition, you can buy as many spices as you want, as long as the total amount of each spice purchased does not exceed your budget. With the spices you have collected, how many mixed spices can you make at most?

Given the number of different types of spices to be used in a mixed spice, your budget, the price per gram of each spice, the amount of each spice on hand, and the ratio of the mixed spices, create a program that calculates the maximum number of grams of mixed spices that can be made. However, the minimum unit for purchasing spices is one gram, and the minimum unit for each spice that can be used when mixing spices is also one gram.

Input

Input is given in the following format.

$N$ $C$
$a_1$
：
$a_N$
$b_1$
：
$b_N$
$x_1$
：
$x_N$

In the first line, the number of spice types $N$ ($2 \leq N \leq 10$) and the budget for mixed spices $C$ ($0 \leq C \leq 1,000$) are given. In the subsequent $N$ lines, the price per gram of the $i$th spice $a_i$ ($1 \leq a_i \leq 10$) is given as an integer. In the following $N$ lines, the quantity $b_i$ ($0 \leq b_i \leq 10$) of the $i$th spice on hand is given as an integer in grams. The following $N$ lines show the ratio of each spice $x_1$:$x_2$:... ($1 \leq x_i \leq 10$) is given as an integer. However, the greatest common divisor of $x_1$,$x_2$,.... ,$x_N$ is 1.

Output

Output the maximum amount of mixed spices that can be made, in grams, on one line.  

Sample Input and Output

Sample Input １

2 100
2
8
5
5
1
1

Sample Output １

30

Sample Input ２

3 100
10
10
10
10
10
2
2
4
3

Sample Output ２

27

---