Bus and Passengers

There is a bus route with N (1 <= N <= 10,000) stops. The stops are numbered 1, 2, ..., N in order. The bus starts at stop 1, travels to stop N, and then returns to stop 1 along the same route.

The bus company usually sends buses from stop 1 at regular intervals so that every customer can ride. Because heavy snow allows only one bus to run, the company must use survey data for K (1 <= K <= 50,000) requested travel sections.

The bus can carry at most C (1 <= C <= 100) people at once. During one round trip, the company wants to take as many customers as possible to their destinations. At each stop, the bus may drop off customers and pick up new ones. Once a customer boards, they cannot get off before reaching their destination.

Write a program that finds the maximum number of customers who can be carried to their destinations.

The first line contains three integers K, N, and C. Each of the next K lines contains three integers S, E (1 <= S, E <= N), and M (1 <= M <= C), describing a requested bus section. S and E are different, and the line means that M customers want to travel from stop S to stop E.

Print the maximum number of customers who can be carried to their destinations.

Carry two customers from stop 1 to stop 3. At stop 2, carry only one of the customers going to stop 8. Drop off the two customers at stop 3, then pick up one customer at stop 4 going to stop 7. Drop that customer off at stop 7, drop off the remaining customer at stop 8, and then pick up two customers going to stop 3. Drop those two customers off at stop 3 and return to stop 1.