問題文

$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$ です。