A Giveaway

shimul12614 DIU Take-Off Programming...
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.

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×n2 \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×n 2 \times n integers as i-th piles 1-st product gift card money as (g[1],g[2],g[3].g[2×n]).(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×n 2 \times n integers as i-th piles 2-st product gift card money as (g[1],g[2],g[3].g[2×n]).(g[1],g[2],g[3]….g[2 \times n]).

1n141 \leq n \leq 14

1m,UCi,BCi,gi10171 \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

Submit

Login to submit.

Statistics

80% Solution Ratio
steinumEarliest, 9M ago
steinumFastest, 0.5s
steinumLightest, 114 MB
steinumShortest, 918B
Toph uses cookies. By continuing you agree to our Cookie Policy.