F - テレポーター 2 (Teleporter 2) Editorial /

Time Limit: 3.5 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

There are N points on a straight path, numbered 1, 2, \ldots, N from left to right. The path is one-way from left to right.

There are also M teleporter devices numbered 1, 2, \ldots, M. By using device i (1 \leq i \leq M), one can warp from point S_i to point T_i (S_i < T_i).

Bitaro is currently at point 1 and wants to reach point N. When Bitaro is at point j (1 \leq j \leq N-1), he can take one of the following actions:

  • Move on foot to point j+1.
  • Choose an i (1 \leq i \leq M) satisfying S_i = j, use device i, and warp to point T_i.

It is known that warp travel places stress on the body. You are concerned about Bitaro's safety, so you decide to destroy zero or more teleporter devices so that, no matter which route Bitaro takes, the number of warp travels is at most K. Device i can be destroyed by paying cost C_i; if so, Bitaro can no longer use that device.

Find the minimum possible total cost you need to pay when destroying zero or more teleporter devices so that, regardless of Bitaro's route, the number of warp travels is at most K.

Input

Read the following data from the standard input.

N M K
S_1 T_1 C_1
S_2 T_2 C_2
\vdots
S_M T_M C_M

Output

Write one line to the standard output containing the minimum possible total cost.

Constraints

  • 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).
  • Given values are all integers.

Subtasks

  1. (5 points) K=1.
  2. (3 points) N \leq 20, M \leq 20.
  3. (29 points) N \leq 500, M \leq 500.
  4. (23 points) N \leq 4\,000, M \leq 4\,000.
  5. (24 points) N \leq 40\,000, M \leq 40\,000.
  6. (16 points) No additional constraints.

Sample Input 1

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

Sample Output 1

4

Consider the case where devices 3 and 4 are destroyed.

Then Bitaro can use only devices 1 and 2. When moving from point 1 to point 8, Bitaro will always make at most one warp travel, so the condition is satisfied.

In this case, the total paid cost is 4. Since it is impossible to make the cost at most 3, the correct output is 4.

This input example satisfies the constraints of all subtasks.

Sample Input 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

Sample Output 2

6

Destroying devices 2 and 5 is optimal.

This input example satisfies the constraints of subtasks 2,3,4,5,6.

Sample Input 3

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

Sample Output 3

0

In this case, there is no need to destroy any device.

This input example satisfies the constraints of subtasks 2,3,4,5,6.

配点 : 100 点

問題文

一本道に N 個の地点があり，左から順に 1, 2, \ldots, N の番号が付けられている．道は左から右への一方通行である．

また，1, 2, \ldots, M の番号が付いた M 個のテレポーター装置がある． 装置 i (1 \leqq i \leqq M) を使用すると地点 S_i から地点 T_i (S_i < T_i) にワープ移動することができる．

ビ太郎は現在地点 1 におり，地点 N に向かおうとしている． ビ太郎が地点 j (1 \leqq j \leqq N-1) にいるときにとることができる行動は次のいずれかである．

  • 地点 j+1 に歩いて移動する．
  • S_i=j を満たす i (1 \leqq i \leqq M) を選ぶ．装置 i を使用し，地点 T_i にワープ移動する．

ワープ移動をすると体に負担がかかることが知られている． ビ太郎の体の安全について心配するあなたは，ビ太郎がどのような経路をとったとしてもワープ移動の回数が K 以下となるよう，0 個以上のテレポーター装置を破壊することにした． テレポーター装置 i はコスト C_i を支払うことで破壊することができ，その場合ビ太郎はその装置を使用することが不可能となる．

ビ太郎がどのような経路をとったとしてもワープ移動の回数が K 以下となるように 0 個以上のテレポーター装置を破壊するとき，支払うコストの総和としてありうる最小値を求めよ．

入力

入力は以下の形式で標準入力から与えられる．

N M K
S_1 T_1 C_1
S_2 T_2 C_2
\vdots
S_M T_M C_M

出力

標準出力に，支払うコストの総和としてありうる最小値を 1 行で出力せよ．

制約

  • 2 \leqq N \leqq 100\,000．
  • 1 \leqq K \leqq M \leqq 100\,000．
  • 1 \leqq S_i < T_i \leqq N (1 \leqq i \leqq M)．
  • 1 \leqq C_i \leqq 10^9 (1\leqq i \leqq M)．
  • 入力される値はすべて整数である．

小課題

  1. (5 点) K=1．
  2. (3 点) N\leqq 20，M\leqq 20．
  3. (29 点) N\leqq 500，M\leqq 500．
  4. (23 点) N\leqq 4\,000，M\leqq 4\,000．
  5. (24 点) N\leqq 40\,000，M\leqq 40\,000．
  6. (16 点) 追加の制約はない．

入力例 1

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

出力例 1

4

装置 3, 4 を破壊した場合を考える．

ビ太郎が使用可能な装置は 1, 2 のみとなる．地点 1 から地点 8 に移動するときにビ太郎がワープ移動をする回数は必ず 1 回以下となるため，条件を満たす．

このとき，支払うコストの総和は 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 の制約を満たす．