A Giveaway

Mr. Tom is the head of ICPC world final organizing committee. For the world final, he comes to Dhaka. For buying some goodies he goes to a departmental store. He sees an interesting thing in this store. This store gives some gift cards on some products by following some rules.

There is n pile of offer products. Each pile contains two products with sequence order as(1-st product, 2-nd product).

Each product contains:

• A single product has a price p[i].

• Also a single product contains 2 x n gift cards collection in a row (g[1], g[2], g[3] ... g[2 x n]) where g[i] denotes the amount of money.

He has m amount of money. He wants to buy those offered products using less than or an equal m amount of money and maximize the total amount of gift card money. But this time buying a product is different.

For buying i-th product:

• He needs at least p[i] amount of money.

• From i-th pile he can buy 1-st product first. More formally ( to buy 2nd product he needs to buy 1-st product first).

• During buying i-th product, he gains i-th gift card money as g[i] from this particular product’s gift card collections.

Input

The first line of input contains an integer n, m - the number of piles and amount of money Mr tom has.

The next two line contains $2 \times n$ integers where:

• the 1-st line contains n integers as 1st product price as (p[1],p[2],p[3],…..p[n]) of i-th piles.

• the 2-nd line contains n integers as 2-nd product price as (p[1],p[2],p[3],…..p[n]) of i-th piles.

Then the next N line as (1,2,3,..N) i-th line where:

• each i-th line contains $2 \times n$ integers as i-th piles 1-st product gift card money as $(g[1],g[2],g[3]….g[2 \times n]).$

Then the next N line as (1,2,3,..N) i-th line where:

• each i-th line contains $2 \times n$ integers as i-th piles 2-st product gift card money as $(g[1],g[2],g[3]….g[2 \times n]).$

$1 \leq n \leq 14$

$1 \leq m, UC_i, BC_i, g_i \leq {10}^{17}$

Output

Print the maximum total price of the gift cards.

Sample

Input	Output
2 1000 39 40 16 89 19 53 35 58 23 45 93 15 9 24 50 21 20 11 59 44	180