O. Operation Mandacaru
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Viação Mandacaru runs a daily route through $$$M$$$ cities in Northeastern Brazil, numbered from $$$1$$$ to $$$M$$$ in the order in which they are visited. The bus used on this route has exactly $$$C$$$ seats.

One day, a system failure simultaneously interrupted $$$N$$$ ticket requests. Although no ticket was issued, the request data was recovered. Passenger $$$i$$$'s request is described by three integers $$$L_i$$$, $$$R_i$$$, and $$$P_i$$$: the passenger wants to board in city $$$L_i$$$, get off in city $$$R_i$$$, and would pay $$$P_i$$$ reais for the ticket.

The company does not allow passengers to choose their seats. Therefore, a request can only be accepted if the bus has an available seat during the entire trip between cities $$$L_i$$$ and $$$R_i$$$. In each city, all passengers whose trip ends there get off before new passengers board. Thus, a passenger boarding in city $$$j$$$ may occupy a seat freed in that same city.

Since all requests were received at the same time, it may be impossible to accept all of them without exceeding the bus capacity on some segment of the route. Always concerned with solving the situation as fairly as possible, especially for its own cash register, Viação Mandacaru decided to choose which tickets will be issued so as to maximize its revenue.

Determine the maximum total value the company can earn by issuing a subset of the requests, without the bus carrying more than $$$C$$$ passengers simultaneously on any segment of the trip.

Input

The first line contains three integers $$$N$$$, $$$M$$$, and $$$C$$$ ($$$1 \leq N \leq 10^{5}$$$, $$$2 \leq M \leq 10^{5}$$$, and $$$1 \leq C \leq 50$$$), representing, respectively, the number of requests, the number of cities on the route, and the number of seats on the bus.

Each of the next $$$N$$$ lines contains three integers $$$L_i$$$, $$$R_i$$$, and $$$P_i$$$ ($$$1 \leq L_i \lt R_i \leq M$$$ and $$$1 \leq P_i \leq 10^{9}$$$), indicating that the passenger from request $$$i$$$ wants to board in city $$$L_i$$$, get off in city $$$R_i$$$, and would pay $$$P_i$$$ reais for the ticket.

Output

Print a single integer: the maximum total value, in reais, that Viação Mandacaru can earn.

Examples
Input
5 5 2
1 3 8
2 5 10
1 2 6
3 5 7
2 4 9
Output
31
Input
4 6 1
1 4 10
1 2 4
2 3 4
3 6 4
Output
12
Note

Explanation for example 1

One optimal possibility is to issue the first four requests, earning $$$8 + 10 + 6 + 7 = 31$$$ reais. Passengers getting off in cities $$$2$$$ and $$$3$$$ free seats before the new passengers board in those cities.

Explanation for example 2

Since the bus has only one seat, it is impossible to issue tickets for trips that share any segment. By issuing the last three requests, the same seat can be reused in cities $$$2$$$ and $$$3$$$, and the company earns $$$4 + 4 + 4 = 12$$$ reais.