Fund Management

Frank manages a closed-end equity fund. The fund collects c US dollars from investors and is managed for m days; when the period ends, every holding is converted back to cash. Frank has chosen n stocks to trade.

Each stock has a fixed lot size s_i (the number of shares in one lot). Buying one lot of stock i on a day when its price is p dollars per share costs p · s_i dollars and decreases the fund's cash; selling one lot on a day when its price is p returns p · s_i dollars and increases the fund's cash. Trading one lot fully occupies a day, so Frank may perform at most one action per day: buy one lot, sell one lot, or do nothing. He may not buy a lot unless the fund currently holds enough cash for the whole lot, and partial lots are not allowed.

To limit risk, at any moment the fund may hold at most k_i lots of stock i, and at most k lots in total across all stocks. The fund starts holding only cash and must also end holding only cash: every lot bought must be sold by the last day.

Knowing every stock's price on every day in advance, determine the maximum amount of cash the fund can hold at the end of the m days.

Assume there is a single price per stock per day at which shares may be bought or sold, and ignore all fees and commissions.

The first line contains c m n k:

• c (0.01 ≤ c ≤ 100000000.00) — the cash collected, given to the cent (up to two digits after the decimal point);
• m (1 ≤ m ≤ 100) — the number of days;
• n (1 ≤ n ≤ 8) — the number of stocks;
• k (1 ≤ k ≤ 8) — the overall limit on the number of lots held at any time.

Then follow 2n lines describing the stocks, two lines per stock:

• the first line contains the stock name followed by two integers s_i and k_i. Here s_i (1 ≤ s_i ≤ 1000000) is the lot size and k_i (1 ≤ k_i ≤ k) is the maximum number of lots of this stock that may be held at any time. A stock name is 1 to 5 uppercase Latin letters (A–Z); all names are distinct.
• the second line contains m prices separated by spaces, the price of that stock on each day. Each price is between 0.01 and 999.99 inclusive, given to the cent.

Cash and prices are written as decimal digits optionally followed by a dot and one or two fractional digits.

Print a single line with the maximum amount of cash the fund can hold at the end of the m days. Format it as an integer number of dollars, a dot, and exactly two digits for the cents (for example, 151205.00). The answer does not exceed 1000000000.00.