题目描述

我们有 $N$ 只骆驼，编号为 $1,2,\\ldots,N$。小 S 决定让它们排成一排。

如果第 $i$ 只骆驼是前 $K_i$ 只骆驼中的一只，则它的幸福值为 $L_i$，否则为 $R_i$。

小 S 希望最大化骆驼们的总幸福值。求骆驼的最大可能总幸福值。

解决给定的 $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$
• 每个输入文件中 $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

• 第一个测试用例中，最佳排列骆驼的顺序是 $2, 1$。
  • 骆驼 $1$ 不是最前面的骆驼，所以它的幸福值为 $10$。
  • 骆驼 $2$ 是最前面的两只骆驼之一，所以它的幸福值为 $15$。
• 第二个测试用例中，最佳排列骆驼的顺序是 $2, 1, 3$。
  • 骆驼 $1$ 是最前面的两只骆驼之一，所以它的幸福值为 $93$。
  • 骆驼 $2$ 是最前面的骆驼，所以它的幸福值为 $71$。
  • 骆驼 $3$ 是最前面的三只骆驼之一，所以它的幸福值为 $57$。