버스

여러 정류장에 승객 그룹이 기다리고 있다. 버스는 1번 정류장에서 출발해 2, 3, ..., N번 정류장을 차례로 지나 N번 정류장에서 운행을 마친다. 버스에는 동시에 최대 C명만 탈 수 있다.

각 그룹은 출발 정류장 S_i, 도착 정류장 E_i, 인원 M_i로 주어진다. 한 그룹의 사람들은 모두 S_i번 정류장에서 E_i번 정류장까지 이동하려고 하며, 버스는 정원을 넘지 않는 범위에서 각 그룹의 일부 또는 전부를 태울 수 있다. 전체 운행 동안 태울 수 있는 승객 수의 최댓값을 구하라.

첫 줄에는 그룹 수 K(1 <= K <= 50,000), 정류장 수 N(1 <= N <= 20,000), 버스 정원 C(1 <= C <= 100)가 공백으로 구분되어 주어진다.

다음 K개 줄에는 각 그룹의 정보 S_i, E_i, M_i가 공백으로 구분되어 주어진다. 이는 M_i명의 승객이 S_i번 정류장에서 타서 E_i번 정류장에서 내리려고 한다는 뜻이다.

버스가 태울 수 있는 승객 수의 최댓값을 출력한다.

한 최적 운행에서는 1번에서 5번까지 2명, 5번에서 8번까지 3명, 8번에서 14번까지 2명, 9번에서 12번까지 1명, 13번에서 14번까지 1명, 14번에서 15번까지 1명을 태워 총 10명을 수송한다.