Description

Original source: SCOI 2010

Recently, lxhgww has become obsessed with stock investment again. After some observation and learning, he has summarized certain patterns in stock market trends.

Through a period of observation, lxhgww predicted the trend of a certain stock over the next $T$ days. On the $i$-th day, the stock's buying price per share is $AP_i$, and the selling price per share is $BP_i$ (it is guaranteed that $AP_i\ge BP_i$ for each $i$). However, unlimited trading is not allowed each day, so the stock exchange stipulates that on the $i$-th day, a single purchase can buy at most $AS_i$ shares, and a single sale can sell at most $BS_i$ shares.

Additionally, the stock exchange has two more rules. To prevent excessive trading, the stock exchange mandates that there must be at least $W$ days between two consecutive trades (a trade is defined as either a buy or a sell on a given day). That is, if a trade occurs on the $i$-th day, then no trades can occur from the $(i+1)$-th day to the $(i+W)$-th day. Moreover, to avoid monopolization, the stock exchange also stipulates that at any time, the number of shares held by an individual cannot exceed $\text{MaxP}$.

Before the first day, lxhgww has a large sum of money (which can be considered infinite) but no stocks. Of course, after $T$ days, lxhgww wants to maximize his profit. Clever programmers, can you help him?

Input Format

The first line of input data contains three integers: $T, \text{MaxP}, W$.

The next $T$ lines represent the stock trends for the $i-1$-th day. Each line contains four integers: $AP_i, BP_i, AS_i, BS_i$.

Output Format

The output data consists of a single line containing a number, representing the maximum profit lxhgww can earn.

Sample 1

5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1

3

Data Range and Hints

For $30\%$ of the data, $0\le W\lt T\le 50, 1\le \text{MaxP}\le 50$;
For $50\%$ of the data, $0\le W\lt T\le 2000, 1\le \text{MaxP}\le 50$;
For $100\%$ of the data, $0\le W\lt T\le 2000, 1\le \text{MaxP}\le 2000, 1\le BP_i\le AP_i\le 1000, 1\le AS_i, BS_i\le \text{MaxP}$.