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:

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:


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×n2 \times n integers where:

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

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

1n141 \leq n \leq 14

1m,UCi,BCi,gi10171 \leq m, UC_i, BC_i, g_i \leq {10}^{17}


Print the maximum total price of the gift cards.


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