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 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 integers as i-th piles 1-st product gift card money as
Then the next N line as (1,2,3,..N) i-th line where:
- each i-th line contains integers as i-th piles 2-st product gift card money as
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 |
