AT_aising2020_e Camel Train

[problemUrl]: https://atcoder.jp/contests/aising2020/tasks/aising2020_e $ 1,2,\ldots,N $ の番号がついた $ 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 $ - $ 1 $ つの入力ファイルにおいて、$ N $ の総和は $ 2\ \times\ 10^5 $ を超えない。 ### Sample Explanation 1 \- $ 1 $ 番目のテストケースにおいて、ラクダ $ 2,1 $ の順で並べるのが最適です。 - ラクダ $ 1 $ は先頭から $ 1 $ 番目以内にいないのでうれしさは $ 10 $ です。 - ラクダ $ 2 $ は先頭から $ 2 $ 番目以内にいるのでうれしさは $ 15 $ です。 - $ 2 $ 番目のテストケースにおいて、ラクダ $ 2,1,3 $ の順で並べるのが最適です。 - ラクダ $ 1 $ は先頭から $ 2 $ 番目以内にいるのでうれしさは $ 93 $ です。 - ラクダ $ 2 $ は先頭から $ 1 $ 番目以内にいるのでうれしさは $ 71 $ です。 - ラクダ $ 3 $ は先頭から $ 3 $ 番目以内にいるのでうれしさは $ 57 $ です。