Stock Trading Profits

Recently, lxhgww has gotten hooked on stock investments. After a period of observation and learning, he has deduced some rules for stock prices. For the next \(T\) days, he has predicted the trend of a certain stock. On the \(i\)-th day, the stock's buy price is given by \(AP_i\) and its sell price is \(BP_i\) (with the guarantee that \(AP_i \geq BP_i\) for each \(i\)). However, due to trading restrictions, on day \(i\) a single buy transaction can purchase at most \(AS_i\) shares, and a single sell transaction can sell at most \(BS_i\) shares.

Moreover, the stock exchange has imposed two additional rules. To discourage excessive trading, there must be an interval of at least \(W\) days between any two transactions (each buy or sell counts as a transaction). That is, if a transaction occurs on day \(i\), then no transactions can take place on days \(i+1\) through \(i+W\). In addition, to avoid monopolization, at any time a person cannot hold more than \(\text{MaxP}\) shares.

Before day 1, lxhgww has an unlimited amount of money but holds zero shares. After \(T\) days, he wishes to maximize his earnings. Can you help him achieve the maximum profit?

inputFormat

The input begins with a line containing three integers: \(T\), \(W\), and \(\text{MaxP}\) — the number of days, the mandatory waiting period between transactions, and the maximum number of shares that can be held, respectively.

Then follow \(T\) lines, each containing four integers: \(AP_i\), \(BP_i\), \(AS_i\), and \(BS_i\). Here, \(AP_i\) is the buy price on day \(i\), \(BP_i\) is the sell price on day \(i\) (with \(AP_i \ge BP_i\)), \(AS_i\) is the maximum number of shares that can be bought on that day, and \(BS_i\) is the maximum number of shares that can be sold on that day.

outputFormat

Output a single integer: the maximum profit that can be obtained by following the rules above. Note that any shares held at the end of day \(T\) must be sold, so the final share count must be zero.

sample

4 0 10
5 4 5 3
3 3 10 10
6 7 5 5
8 9 10 10

50