버스
시간 제한2초메모리 제한128 MB
여러 승객 그룹이 각기 다른 정류장 구간을 이동할 때, 어느 구간에서도 버스 정원 C를 넘지 않도록 태울 인원을 골라 총 승객 수를 최대화하는 문제입니다.
문제
여러 정류장에 승객 그룹이 기다리고 있다. 버스는 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명을 수송한다.