Tram#460
Every morning, people travel by tram along the same route from the outskirts to the city center. Over time, they have gotten to know each other fairly well. To ensure fairness, they want to decide who should sit and who should stand, and between which stops these decisions should be made. All stops are numbered from to .
One of the passengers is an expert in mathematical modeling. He suggests considering the value of the total satisfaction of the passengers. For each -th passenger, two values are assigned: a_i and b_i. If the passenger sits for one segment between two stops, a_i is added to the total satisfaction; if the passenger stands, b_i is added instead.
There are seats in the tram. Passengers can instantly sit down or stand up at any stop. Furthermore, some passengers prefer to stand even if seats are available (for them, a_i < b_i).
Given the values a_i and b_i for each -th passenger, as well as the stops at which each passenger boards (c_i) and leaves (d_i) the tram, write a program to compute the maximum possible total satisfaction.
The first line contains three space-separated integers , , and (1 \leq n, m, p \leq 100\ 000; 2 \leq p): the number of passengers, number of seats, and number of stops on the route, respectively.
Each of the next lines describes a passenger with four integers a_i, b_i, c_i, d_i: the first two are the satisfaction values for sitting and standing, the third is the boarding stop, and the fourth is the alighting stop (-10^6 \leq a_i, b_i \leq 10^6; 1 \leq c_i < d_i \leq p).
Output a single integer: the maximum total satisfaction the passengers can achieve.
Example comment
Maximum total satisfaction is achieved as follows:
At the first stop, the second and third passengers board and sit down;
At the second stop, the first and fourth passengers board, and the second passenger gives up their seat to the first;
At the third stop, the first and third passengers stand up and leave, while the second and fourth sit in their places;
At the fourth stop, the first and third passengers leave.
Example 1