Page not loading? Try clicking here.
Placeholder

#8081
Subtask

하행 승강기 1.5s 1024MB

Problems

N명의 사람들이 모두 층이 다른 독립된 방에 위치해 있다.

각 방은 단 하나의 승강기를 통하여 연결이 되어있고, 사람들은 승강기를 통하여 본인의 방에 있는 물품을 아래 층으로 보낼 수 있다.

단, 승강기가 한 번에 담을 수 있는 물품의 최대 용량은 C이다.

만약, 5층에서 2층으로 물품을 6개 보내는데 C가 10인 상황이라면, 4층이나 3층에서 아래 층으로 보낼 수 있는 물품의 최대 개수는 4개이다.

사람들은 각자 특정한 층으로 특정한 개수의 물품을 내려보내고 싶어 하지만, 승강기가 한 번에 옮길 수 있는 최대 용량이 정해져 있기에 서로 적절히 협의를 해야한다.

승강기는 전기세를 아끼기 위하여 하루에 딱 한번 N층에서 출발하여 1층까지 운행을 하게 되는데, 이 때 사람들이 아래층으로 내려보낼 수 있는 물건의 총량의 최댓값이 얼마인지 구하는 프로그램을 작성하시오.


Input

첫 줄에 세 정수 N, C, M이 주어진다. (1 \le N,M \le 500,000, 1 \le C \le 10^9)

이어 M줄에 걸쳐 세 정수 a, b, c가 주어지는데, 이는 a층에서 b층으로 c개의 물품을 내려보내고 싶다는 의미다. (1 \le b < a \le N, 1 \le c \le 2,000)


Output

첫 줄에 내려보낸 물건의 총량은 최대값을 출력한다.


Subtask

# Score Condition
#110

물품의 최대 용량은 1이다. 즉, C = 1이다.

#220

N,C,M \le 100

#330

모든 물품은 1층으로만 배송이 내려 보낼 수 있다. 즉, b=1이다.

#440

추가 제한 없음


Example #1

5 10 4
5 3 6
5 1 8
4 2 7
3 2 6
16

5층에 있는 사람은 3층에 6개의 물건을 보내고 싶고, 1층에는 8개의 물건을 보내고 싶어한다.

4층에 있는 사람은 2층에 7개의 물건을 보내고 싶어한다.

3층에 있는 사람은 2층에 6개의 물건을 보내고 싶어한다.

이 때, 승강기의 최대 적재량은 10이기에 아래와 같은 선택을 통해 총 16개의 물건이 옮겨질 수 있다.

  • 5층에서 3층에 보낼 6개의 물건을 승강기에 싣고,

  • 4층에서 2층에 보낼 4개의 물건을 승강기에 싣고,

  • 3층에서 5층에서 보낸 물건을 받은 후, 2층에 보낼 6개의 물건을 승강기에 싣고,

  • 2층에서 4층과 3층에서보낸 물건을 받으면 된다.


Example #2

5 10 5
2 1 2
4 3 6
5 3 5
3 2 9
4 1 3
21


Source

klee
You must sign in to write code.