시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 59 9 7 18.919%

문제

N(1≤N≤10,000)개의 정류장을 지나는 버스가 있다. 정류장은 차례로 1, 2, …, N번의 번호가 붙어 있고, 버스는 1번 정류장에서 출발하여 N번 정류장까지 간 후, 다시 1번 정류장으로 돌아오게 된다.

버스회사에서는 주기적으로 1번 정류장에서 버스를 출발시켜서 모든 손님들이 버스를 이용할 수 있도록 하고 있었는데, 겨울철에 눈이 많이 오는 바람에 한 대의 버스밖에 운행하지 못 하게 되었다. 불행 중 다행으로 회사에서는 고객들이 버스를 이용하는 구간을 K(1≤K≤50,000)개 조사해 둔 상태이다.

버스는 최대 C(1≤C≤100)명을 태울 수 있다. 회사 측에서는 사전에 조사해 둔 자료를 바탕으로, 한 바퀴를 도는(1번 정류장에서 N번 정류장까지 갔다가 다시 1번 정류장으로 돌아오는) 동안 가급적이면 많은 고객들을 목적지까지 태워 주려고 한다. 각 정류장에서 버스는 사람을 내려 줄 수도 있고, 사람을 태울 수도 있다. 단, 버스에 한 밴 태운 고객들은 목적지에 도착하기 전에는 내려줄 수 없다.

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력

4 8 3
1 3 2
2 8 3
4 7 1
8 3 2

예제 출력

6

힌트

1번 정류장에서 3번 정류장으로 가는 고객을 두 명 태운다. 2번 정류장에서는 8번 정류장으로 가는 고객을 한 명 태운다(세 명을 다 태울 필요는 없다). 3번 정류장에서 두 명의 고객을 내려 주고, 4번 정류장에서는 7번 정류장으로 가는 고객을 한 명 태운다. 7번 정류장에서 한 명의 고객을 내려 주고, 8번 정류장에서 남은 한 명의 고객을 내려 준 뒤, 3번 정류장으로 가는 고객을 두 명 태운다. 이 고객들을 3번 정류장에 내려 주고, 다시 1번 정류장으로 돌아온다.

출처

  • 문제의 오타를 찾은 사람: baek1134