E - Camel Train 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

1,2,\ldots,N の番号がついた N 頭のラクダがいます。 すぬけ君はラクダたちを一列に並べることにしました。

ラクダ i が先頭から K_i 番目以内にいるときのうれしさは L_i です。 そうでない場合のうれしさは R_i です。

すぬけ君はラクダたちのうれしさの総和を最大化したいです。 ラクダたちのうれしさの総和としてありうる値のうち最大値を求めてください。

テストケースは T 個与えられるので、それぞれについて答えを求めてください。

制約

  • 与えられる入力は全て整数
  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 2 \times 10^{5}
  • 1 \leq K_i \leq N
  • 1 \leq L_i, R_i \leq 10^9
  • 1 つの入力ファイルにおいて、N の総和は 2 \times 10^5 を超えない。

入力

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

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

各ケースは以下の形式で与えられる。

N
K_1 L_1 R_1
\vdots
K_N L_N R_N

出力

T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。

入力例 1

3
2
1 5 10
2 15 5
3
2 93 78
1 71 59
3 57 96
19
19 23 16
5 90 13
12 85 70
19 67 78
12 16 60
18 48 28
5 4 24
12 97 97
4 57 87
19 91 74
18 100 76
7 86 46
9 100 57
3 76 73
6 84 93
1 6 84
11 75 94
19 15 3
12 11 34

出力例 1

25
221
1354
  • 1 番目のテストケースにおいて、ラクダ 2,1 の順で並べるのが最適です。
    • ラクダ 1 は先頭から 1 番目以内にいないのでうれしさは 10 です。
    • ラクダ 2 は先頭から 2 番目以内にいるのでうれしさは 15 です。
  • 2 番目のテストケースにおいて、ラクダ 2,1,3 の順で並べるのが最適です。
    • ラクダ 1 は先頭から 2 番目以内にいるのでうれしさは 93 です。
    • ラクダ 2 は先頭から 1 番目以内にいるのでうれしさは 71 です。
    • ラクダ 3 は先頭から 3 番目以内にいるのでうれしさは 57 です。

Score : 500 points

Problem Statement

We have N camels numbered 1,2,\ldots,N. Snuke has decided to make them line up in a row.

The happiness of Camel i will be L_i if it is among the K_i frontmost camels, and R_i otherwise.

Snuke wants to maximize the total happiness of the camels. Find the maximum possible total happiness of the camel.

Solve this problem for each of the T test cases given.

Constraints

  • All values in input are integers.
  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 2 \times 10^{5}
  • 1 \leq K_i \leq N
  • 1 \leq L_i, R_i \leq 10^9
  • The sum of values of N in each input file is at most 2 \times 10^5.

Input

Input is given from Standard Input in the following format:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

Each case is given in the following format:

N
K_1 L_1 R_1
\vdots
K_N L_N R_N

Output

Print T lines. The i-th line should contain the answer to the i-th test case.

Sample Input 1

3
2
1 5 10
2 15 5
3
2 93 78
1 71 59
3 57 96
19
19 23 16
5 90 13
12 85 70
19 67 78
12 16 60
18 48 28
5 4 24
12 97 97
4 57 87
19 91 74
18 100 76
7 86 46
9 100 57
3 76 73
6 84 93
1 6 84
11 75 94
19 15 3
12 11 34

Sample Output 1

25
221
1354
  • In the first test case, it is optimal to line up the camels in the order 2, 1.
    • Camel 1 is not the frontmost camel, so its happiness will be 10.
    • Camel 2 is among the two frontmost camels, so its happiness will be 15.
  • In the second test case, it is optimal to line up the camels in the order 2, 1, 3.
    • Camel 1 is among the two frontmost camels, so its happiness will be 93.
    • Camel 2 is the frontmost camel, so its happiness will be 71.
    • Camel 3 is among the three frontmost camels, so its happiness will be 57.