Bus

Passenger groups are waiting at several bus stops. The bus starts at stop 1, visits stops 2, 3, ..., N in order, and finishes at stop N. At any moment, at most C people can be on the bus.

Each group is described by a start stop S_i, an end stop E_i, and a size M_i. All people in the group want to travel from S_i to E_i, and the bus may carry any part or all of a group as long as the capacity limit is never exceeded. Find the maximum total number of people the bus can carry.

The first line contains three integers K (1 <= K <= 50,000), N (1 <= N <= 20,000), and C (1 <= C <= 100): the number of groups, the number of stops, and the bus capacity.

Each of the next K lines contains three integers S_i, E_i, and M_i. This means M_i people want to board at stop S_i and get off at stop E_i.

Print the maximum number of people the bus can carry.

One optimal trip carries 2 people from stop 1 to stop 5, 3 people from stop 5 to stop 8, 2 people from stop 8 to stop 14, 1 person from stop 9 to stop 12, 1 person from stop 13 to stop 14, and 1 person from stop 14 to stop 15, for a total of 10 people.