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]).$