AT_aising2020_e.Camel Train

有 $N$ 头编号为 $1,2,\ldots,N$ 的骆驼。すぬけ君打算将这些骆驼排成一列。

当第 $i$ 头骆驼排在队列的前 $K_i$ 个位置时，它的快乐值为 $L_i$。否则，它的快乐值为 $R_i$。

すぬけ君想要让所有骆驼的快乐值之和最大。请你求出所有可能的快乐值总和中的最大值。

有 $T$ 组测试数据，请分别输出每组的答案。

输入按以下格式从标准输入给出。

$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 \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$。

样例解释 1

• 在第 $1$ 组测试数据中，将骆驼按 $2,1$ 的顺序排列最优。
  • 骆驼 $1$ 不在前 $1$ 个位置，所以快乐值为 $10$。
  • 骆驼 $2$ 在前 $2$ 个位置，所以快乐值为 $15$。
• 在第 $2$ 组测试数据中，将骆驼按 $2,1,3$ 的顺序排列最优。
  • 骆驼 $1$ 在前 $2$ 个位置，所以快乐值为 $93$。
  • 骆驼 $2$ 在前 $1$ 个位置，所以快乐值为 $71$。
  • 骆驼 $3$ 在前 $3$ 个位置，所以快乐值为 $57$。

由 ChatGPT 4.1 翻译