题目描述

在一条直路上有 $N$ 个点，从左到右依次编号为 $1,2,\dots,N$。这条路是从左向右的单行道。

还有 $M$ 个传送设备，编号为 $1,2,\dots,M$。使用设备 $i$（$1 \leq i \leq M$），可以从点 $S_i$ 传送到点 $T_i$（$S_i < T_i$）。

Bitaro 目前在点 $1$，并希望到达点 $N$。当 Bitaro 在点 $j$（$1 \leq j \leq N-1$）时，他可以采取以下行动之一：

• 步行移动到点 $j+1$。
• 选择一个满足 $S_i = j$ 的 $i$（$1 \leq i \leq M$），使用设备 $i$，并传送到点 $T_i$。

已知传送旅行会对身体造成压力。你很担心 Bitaro 的安全，因此你决定摧毁零个或多个传送设备，以便无论 Bitaro 采取哪条路线，传送旅行的次数最多为 $K$ 次。支付 $C_i$ 的代价可以摧毁设备 $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$

输出格式

向标准输出写入一行，包含最小的可能总代价。

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

4

12 7 2
1 5 3
4 8 2
2 4 5
2 4 8
7 9 4
9 11 7
3 10 5

6

6 3 2
1 4 2
2 5 4
3 6 3

0

提示

样例 1

考虑摧毁设备 $3$ 和 $4$ 的情况。

这样 Bitaro 只能使用设备 $1$ 和 $2$。当从点 $1$ 移动到点 $8$ 时，Bitaro 将始终最多进行一次传送旅行，因此条件得到满足。

在这种情况下，支付的总代价为 $4$。由于不可能使代价最多为 $3$，因此正确的输出是 $4$。

这个输入样例满足所有子任务的约束条件。

样例 2

摧毁设备 $2$ 和 $5$ 是最优的。

这个输入样例满足子任务 $2,3,4,5,6$ 的约束条件。

样例 3

在这种情况下，不需要摧毁任何设备。

这个输入样例满足子任务 $2,3,4,5,6$ 的约束条件。

约束条件

• $2 \leq N \leq 100000$。
• $1 \leq K \leq M \leq 100000$。
• $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$)。
• 给定的值均为整数。

子任务

1. (5 分) $K = 1$。
2. (3 分) $N \leq 20$, $M \leq 20$。
3. (29 分) $N \leq 500$, $M \leq 500$。
4. (23 分) $N \leq 4000$, $M \leq 4000$。
5. (24 分) $N \leq 40000$, $M \leq 40000$。
6. (16 分) 无附加限制。