시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 25 16 7 58.333%

문제

포천 주민들은 여러 버스 정류장에서 버스를 기다리고 있다. 하지만 안타깝게도 버스는 이 모든 사람들을 수용할 수 있는 크기가 되지 못한다. 

문제는 정류장의 개수 N과 M개의 그룹에 대해 현재 기다리는 정류장 번호와 내릴 정류장 번호가 주어지면 1번 정류장에서 출발하여 N번 정류장까지 운행할 때 최대 태울 수 있는 인원을 구하는 것이다. 단, 버스는 1, 2, …, N번 정류장 순서로 방문한다.

입력

첫 줄에는 그룹의 수 K(1 ≤ K ≤ 50,000)와 정류장 개수 N(1 ≤ N ≤ 20,000)과 버스의 최대 수용 인원 C(1 ≤ C ≤ 100)가 공백으로 구분되어 주어진다. 두 번째 줄부터 K+1번째 줄까지 각 줄에 대해 K개의 그룹에 대한 정보가 담긴 Si, Ei, Mi가 주어지는데 이는 이 그룹은 총 Mi명이고 Si번 정류장에서 출발하여 Ei번 정류장에서 내릴려고 한다는 의미이다.

출력

첫 줄에 최대 수송 인원을 출력한다.

예제 입력

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

예제 출력

10

힌트

버스가 1번->5번으로 가는 2명인 그룹과 5번->8번으로 가는 3명인 그룹, 8번->14번으로 가는 2명인 그룹, 9번->12번으로 가는 1명인 그룹, 13번->14번으로 가는 1명인 그룹, 14번->15번으로 가는 1명인 그룹을 태우면 총 10명을 수송한 셈이 된다.

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO February 2009 Contest > Gold 1번

  • 문제를 번역한 사람: author6
  • 문제의 오타를 찾은 사람: dotorya