# A Giveaway

Limits 2s, 1.0 GB

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.

• 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

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

180