← 返回题目列表

AtCoder · aising2020_e

E. 骆驼火车

中文机器翻译题面 查看原题

分数: 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.