문제
정올택배회사( JLC - Jungol Logistics Corp )에서는 여러가지 상황에 대비하여
지점 간에 택배 시뮬레이션을 계획하고 있다.
가장 문제가 되는 경우가 택배 차량들의 적재용량에 비하여 택배주문이 많은 경우인데,
이 경우 하나의 차량은 가능하면 최대 수량을 배달할 수 있도록 해야한다.
이를 위하여 택배 지점들에 번호를 부여하고 A지점에서 B지점으로 택배를 운송하는 시뮬레이션을 계획하고 있다.
여러 가지 복잡한 상황이 있게 마련이지만 일단은 다음과 같은 조건으로 한정한다.
1. 한 대의 차량만으로 시뮬레이션 한다.
2. 차량은 1번 지점에서 N번지점으로 일방향으로만 움직인다.
3. A지점에서 B지점으로의 택배의뢰 역시 A지점 번호가 B지점 번호보다 항상 작다.
4. 차량의 적재용량을 허용하는 범위만 배송한다. 따라서 일부 의뢰는 처리하지 못하거나 일부만 처리할 수도 있다.
5. 일단 배송차에 적재한 물품은 중간에 내릴 수 없으며 목적지까지 배송하여야 한다.
택배 지점의 개수, 트럭의 용량, 물품 개수가 주어질 때,
트럭 한 대로 배송할 수 있는 최대 개수를 구하는 프로그램을 작성하시오.
단, 받는 지점번호는 보내는 지점번호보다 항상 크다.
입력
입력의 첫 행은 지점 수 N과 트럭의 적재용량 C가 빈칸을 사이에 두고 주어진다.
N은 2이상 300,000 이하 정수이고, C는 1이상 1,000,000 이하 정수이다.
다음 줄에, 보내는 물품의 개수 M이 주어진다.
M은 1이상 1,000,000 이하 정수이다.
다음 M개의 각 줄에 물품을 보내는 지점번호, 물품을 받는 지점번호,
보내는 물품 개수(1이상 1,000,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다.
박스를 받는 지점번호는 보내는 지점번호보다 크다.
출력
한 행에 트럭 한 대로 배송할 수 있는 최대 물품 수를 출력한다.
예제 #1
11 1000
3
1 5 147
1 7 438
1 11 100
685
예제 #2
3 12345
2
1 2 12345
2 3 12345
24690
예제 #3
20 5000
10
11 14 1576
5 14 2539
10 14 2314
3 14 1072
6 15 1005
13 14 2432
10 15 549
14 15 3713
7 15 962
3 15 722
8713
출처
comkiwer
로그인해야 코드를 작성할 수 있어요.