Veshy has been playing too much 8-ball pool recently, so to cure his addiction, he has turned to collecting pool cue balls instead. While looking into the market for cue balls, he realizes that there is a lot of money to be made. Each month, he can buy and sell a maximum of $X_i$ and $Y_i$ cue balls at a price of $b_i$ and $s_i$ respectively for each month $m_i$. Cue balls, being very valuable, also cost $M$ maintenance (per held cue ball) to upkeep per month. Being Veshy's best friend, you wish to help him maximize his profits over the course of $N$ months. Since Veshy is looking at very long term investments, help him by writing a program!

Constraints

For all subtasks:

$1\le N\le {10}^4$

$1\le M\le {10}^4$

$1\le X_i,Y_i\le 100$

$1\le b_i,s_i\le {10}^4$

Veshy can only hold up to $100$ cue balls at any time.

Veshy can borrow money to buy cue balls (go into debt), but he can never sell more cue balls than he possesses.

Veshy has to wait at least 1 month before selling the cue balls he buys.

Note for Python users: To pass this question using Python you must select the PyPy interpreter instead of the normal one.

Subtask 1 [20%]

$1\le N\le 20$

Subtask 2 [30%]

$1\le N\le {10}^3$

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line will contain two space-separated integers, $N$ and $M$. The following $N$ lines will contain 4 space-separated integers, $X_i$, $Y_i$, $b_i$, and $s_i$ for month $m_i$.

Output Specification

Output the maximum profit Veshy can make by the end of the $N$ month period.

Sample Input 1

3 1
5 3 1 2
3 4 3 2
1 5 2 10

Sample Output 1

35

Explanation of Sample Output 1

Veshy can buy $5$ cue balls on the first month for a price of $1$ dollar each. He can then hold on to these cue balls until the last month, where he can sell them for a price of $10$ dollars each. Since the cost of maintenance is $1$ dollar, and Veshy is holding onto those $5$ cue balls for $2$ months, Veshy's total profit would be $50-5\times 1-5\times 2=35$ dollars.

Sample Input 2

3 100
2 2 100 1
10 5 100 1
1 5 10000 1

Sample Output 2

0

Explanation of Sample Output 2

Here, the best move that Veshy could make is to not invest in the market at all! Buying any amount of cue balls on any month will always result in a loss.