有一条直路，上面有 $N$ 个点，从左到右编号为 $1, 2, \dots, N$。这条路是单向的，只能从左向右走。

此外还有 $M$ 个传送装置，编号为 $1, 2, \dots, M$。使用装置 $i$ ($1 \le i \le M$)，可以从点 $S_i$ 瞬间移动到点 $T_i$ ($S_i < T_i$)。

Bitaro 目前在点 $1$，想要到达点 $N$。当 Bitaro 在点 $j$ ($1 \le j \le N - 1$) 时，他可以采取以下任一行动：

• 步行移动到点 $j + 1$。
• 选择一个满足 $S_i = j$ 的装置 $i$ ($1 \le i \le M$)，使用该装置并瞬间移动到点 $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 \le N \le 100\,000$
• $1 \le K \le M \le 100\,000$
• $1 \le S_i < T_i \le N$ ($1 \le i \le M$)
• $1 \le C_i \le 10^9$ ($1 \le i \le M$)
• 所有输入值均为整数。

子任务

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

样例

样例输入 1

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

样例输出 1

4

说明 1

考虑销毁装置 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

销毁装置 2 和 5 是最优的。 该输入样例满足子任务 2, 3, 4, 5, 6 的限制。

样例输入 3

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

样例输出 3

0

说明 3

在这种情况下，无需销毁任何装置。 该输入样例满足子任务 2, 3, 4, 5, 6 的限制。