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 翻译