分数: 500 点
问题陈述
我们有 N 骆驼编号 1,2,\ldots,N。 斯努克决定让他们排成一排。
骆驼的幸福 i 将是 L_i 如果它在 K_i 最前面的骆驼,以及 R_i 否则。
Snuke 希望最大化骆驼的总幸福感。求骆驼的最大可能总幸福感。
解决每个问题 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.