eolymp
bolt
Try our new interface for solving problems

Tram

Time limit 5 seconds
Memory limit 64 MiB

On the outskirts of the city center every morning for a ride in a tram route N people. For a long time, they travel well enough to know each other. To no one was hurt, they want to decide who among them and between any route stops should sit and who should stand. All stops are numbered from 1 to P.

One of the passengers was an expert in the theory of mathematical modeling. He suggested that the value of the total satisfaction of passengers. For each i-th passenger he appreciated the two values - a_{i }and_{ }b_i. If within one journey between stops a passenger sits, it is added to the total satisfaction of a_i, but if he is then added b_i.

Just M tram seats. Get up and sit down passengers can instantly at any stop. In addition, some passengers prefer to ride standing up, even if the tram is free (for them a_i < b_i).

Need to write a program that calculates the value of the maximum attainable total satisfaction, if for each i-th passenger known quantities a_i and b_i, as well as the number of stops, on which he sits down and goes out of the tram.

Input data

The first line of the input file contains three space-separated integers N, M and P — the number of passengers, number of seats and number of stops on the route, respectively (1N, M, P100 000; 2P).

Each of the next N lines contains information on a regular passenger in the form of four integers a_i, b_i, c_i, d_i:, where the first two numbers define the contribution to the setting of happiness, the third - the number of stops at which a passenger sits down in the tram, and the last - the number of stop, where he comes from a tram (-10^6a_i, b_i10^6; 1c_i < d_iP).

Output data

In the output file should display a single integer - the maximum total satisfaction, which can make the passengers.

Comment example

Maximum total satisfaction is achieved as follows:

  • At the first stop and sit down are the second and third passengers;

  • At the second stop are the first and fourth passengers, the second behind first place;

  • At the third stop rise and fall first and third passenger, second and fourth sit on their seats;

  • At the fourth stop release of the first and third passengers.

Examples

Input example #1
1 1 2
-1 0 1 2
Output example #1
0
Source 2009 Областная олимпиада школьников по информатике, Вологда, Задача C