分数: 100 点
问题陈述
有 N 直线路径上的点,编号 1, 2, \ldots, N 从左到右。 该路径是从左到右的单向路径。
还有 M 传送器设备编号 1, 2, \ldots, M。 通过使用设备 i (1 \leq i \leq M),可以从点扭曲 S_i 来点 T_i (S_i < T_i).
Bitaro 目前处于该位置 1 并想要达到目标 N。 当比特罗在位时 j (1 \leq j \leq N-1),他可以采取以下操作之一:
- 步行至点 j+1.
- 选择一个 i (1 \leq i \leq M) 满意 S_i = j,使用设备 i,并扭曲到点 T_i.
众所周知,曲速旅行会给身体带来压力。 你担心Bitaro的安全,所以决定摧毁零个或多个传送装置,这样,无论Bitaro走哪条路线,曲速旅行的次数最多为 K。 设备 i 可以通过支付费用来破坏 C_i;如果是这样,Bitaro 将无法再使用该设备。
找出摧毁零个或多个传送器设备时需要支付的最小可能总成本,以便无论 Bitaro 的路线如何,曲速旅行的次数最多为 K.
输入
从标准输入读取以下数据。
N M K S_1 T_1 C_1 S_2 T_2 C_2 \vdots S_M T_M C_M
输出
将一行写入标准输出,其中包含可能的最小总成本。
约束
- 2 \leq N \leq 100\,000.
- 1 \leq K \leq M \leq 100\,000.
- 1 \leq S_i < T_i \leq N (1 \leq i \leq M).
- 1 \leq C_i \leq 10^9 (1 \leq i \leq M).
- 给定值均为整数。
子任务
- (5 点) K=1.
- (3 点) N \leq 20, M \leq 20.
- (29 点) N \leq 500, M \leq 500.
- (23 点) N \leq 4\,000, M \leq 4\,000.
- (24 点) N \leq 40\,000, M \leq 40\,000.
- (16 点)没有额外的限制。
示例输入 1
8 4 1 1 4 3 2 3 5 3 6 2 5 8 2
示例输出 1
4
考虑设备 3 和 4 被摧毁。
那么 Bitaro 只能使用设备 1 和 2。 从点移动时 1 来点 8,Bitaro 总是最多进行一次曲速旅行,因此满足条件。
在这种情况下,支付的总成本为 4。 因为最多不可能做出成本 3,正确的输出是 4.
该输入示例满足所有子任务的约束。
示例输入 2
12 7 2 1 5 3 4 8 2 2 4 5 2 4 8 7 9 4 9 11 7 3 10 5
示例输出 2
6
销毁设备 2 和 5 是最佳的。
该输入示例满足子任务的约束 2,3,4,5,6.
示例输入 3
6 3 2 1 4 2 2 5 4 3 6 3
示例输出 3
0
在这种情况下,无需销毁任何设备。
该输入示例满足子任务的约束 2,3,4,5,6.