버스와 승객

N(1 <= N <= 10,000)개의 정류장을 지나는 버스가 있다. 정류장에는 차례로 1, 2, ..., N번 번호가 붙어 있다. 버스는 1번 정류장에서 출발해 N번 정류장까지 간 뒤, 같은 길을 따라 다시 1번 정류장으로 돌아온다.

버스 회사는 평소 1번 정류장에서 주기적으로 버스를 출발시켜 모든 손님이 버스를 이용할 수 있게 했지만, 눈이 많이 와서 한 대만 운행할 수 있게 되었다. 다행히 회사는 손님들이 이용하려는 구간 K(1 <= K <= 50,000)개를 미리 조사해 두었다.

버스에는 최대 C(1 <= C <= 100)명까지 탈 수 있다. 회사는 조사한 자료를 바탕으로, 버스가 한 바퀴 도는 동안 목적지까지 데려다줄 수 있는 손님의 수를 최대화하려고 한다. 각 정류장에서 버스는 손님을 내려 주거나 태울 수 있다. 단, 한 번 태운 손님은 목적지에 도착하기 전에는 내릴 수 없다.

목적지까지 태워 줄 수 있는 손님의 최대 수를 구하는 프로그램을 작성하시오.

첫째 줄에 세 정수 K, N, C가 주어진다. 다음 K개의 줄에는 손님들의 버스 이용 구간을 나타내는 세 정수 S, E(1 <= S, E <= N), M(1 <= M <= C)이 주어진다. S와 E는 서로 다르며, 이는 S번 정류장에서 E번 정류장까지 가려는 손님이 M명 있다는 뜻이다.

첫째 줄에 목적지까지 태워 줄 수 있는 손님의 최대 수를 출력한다.

1번 정류장에서 3번 정류장으로 가는 손님 두 명을 태운다. 2번 정류장에서는 8번 정류장으로 가는 손님 한 명만 태운다. 3번 정류장에서 두 명을 내려 주고, 4번 정류장에서 7번 정류장으로 가는 손님 한 명을 태운다. 7번 정류장에서 한 명을 내려 주고, 8번 정류장에서 남은 한 명을 내려 준 뒤 3번 정류장으로 가는 손님 두 명을 태운다. 이 두 명을 3번 정류장에서 내려 주고 1번 정류장으로 돌아온다.