Description

Recently, $\text{lxhgww}$ has gotten into stock investing again. After a period of observation and learning, he summarized some patterns in stock prices.

Over time, $\text{lxhgww}$ predicted the movement of a certain stock for the next $T$ days. On day $i$, the buy price per share is $AP_i$, and the sell price per share is $BP_i$ (the data guarantees that for every $i$, $AP_i \geq BP_i$). However, trading cannot be unrestricted each day, so the exchange stipulates that in a single buy on day $i$, you can purchase at most $AS_i$ shares, and in a single sell on day $i$, you can sell at most $BS_i$ shares.

In addition, the exchange has two more rules. To avoid excessive trading, the exchange requires that between any two transactions (a buy or a sell on any day counts as one transaction), there must be at least $W$ days in between. That is, if a transaction occurs on day $i$, then from day $i+1$ to day $i+W$ (inclusive), no transactions are allowed. Also, to prevent monopolies, the exchange mandates that at any time, the number of shares a person holds cannot exceed $\text{MaxP}$.

Before day $1$, $\text{lxhgww}$ has a large amount of cash (consider it as unlimited cash), but no stock. Of course, after $T$ days, $\text{lxhgww}$ wants to earn as much money as possible. Smart programmers, can you help him?

Input Format

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

The next $T$ lines describe the stock data. The $i$-th line corresponds to day $i$ and contains $4$ integers, namely $AP_i,\ BP_i,\ AS_i,\ BS_i$.

Output Format

Output a single number: the maximum amount of money $\text{lxhgww}$ can earn.

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

3

Hint

• For 30% of the testdata, $0 \leq W < T \leq 50$, $1 \leq \text{MaxP} \leq 50$.
• For 50% of the testdata, $0 \leq W < T \leq 2000$, $1 \leq \text{MaxP} \leq 50$.
• For 100% of the testdata, $0 \leq W < T \leq 2000$, $1 \leq \text{MaxP} \leq 2000$.
• For all testdata, $1 \leq BP_i \leq AP_i \leq 1000$, $1 \leq AS_i,BS_i \leq \text{MaxP}$.

Translated by ChatGPT 5