#942. 货物运输

货物运输

样例下载

题目描述

NN 个货仓分布在一条直线上,自左向右依次编号为 11 ~ NN。

有 KK 批货物需要运输,第 ii 批货物共 TiT_i 吨,当前正存放于货仓 AiA_i 中,需要运往货仓 BiB_i。

现在有一辆载重量为 MM 吨的货车,要从左向右依次经过 NN 个货仓运输货物。货车只会从左到右单向行驶一次。经过任意一个货仓,货车都可以选择装载或者卸载货物。在运输过程中,货车不能超载。

问:货车最多能把多少吨货物运输到目的地?

输入格式

第一行:三个整数:K,N,MK, N, M

接下来 KK 行:每行三个整数 Ai,Bi,TiA_i, B_i, T_i

输出格式

一个整数,表示答案。

样例输入

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

样例输出

7

样例解释

方案不唯一,以下是一种可能方案:

货车可以把 22 吨货物从 11 运输到 33,把 11 吨货物从 22 运输到 44,把 11 吨货物从 33 运输到 44,把 33 吨货物从 55 运输到 1010。

共计运输 2+1+1+3=72 + 1 + 1 + 3 = 7 吨。

数据范围

40% 的数据:1≤K,N≤201 ≤ K, N ≤ 20

100% 的数据:1≤N≤2×1041 ≤ N ≤ 2×10^4, 1≤K≤5×1041 ≤ K ≤ 5×10^4, 1≤M≤1001 ≤ M ≤100, 1≤Ai<Bi≤N1 ≤ A_i < B_i ≤ N,1≤Ti≤N1 ≤ T_i ≤ N