Tram
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
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 (1 ≤ N, M, P ≤ 100 000; 2 ≤ P).
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^6 ≤ a_i, b_i ≤ 10^6; 1 ≤ c_i < d_i ≤ P).
Output
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.