AT_abc474_e One Time Coupon

ある店では $ N $ 種類の商品が売られています。各商品は何回でも購入することができます。 $ i $ 種類目 $ (1\le i\le N) $ の商品は以下の $ 2 $ 通りの方法で買うことができます： - クーポンを使わずに $ A_i $ 円で購入し、クーポンを $ 1 $ 枚もらう。 - クーポンを $ 1 $ 枚使い、 $ B_i $ 円で購入する。 最初、あなたはクーポンを $ 1 $ 枚も持っていません。 全ての商品を $ 1 $ 回以上購入するために必要な金額の最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

各テストケースに対する答えを順に改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 例えば以下のように行動することで $ 23 $ 円で全ての商品を $ 1 $ 回以上購入することができます： - $ 2 $ 種類目の商品をクーポンを使わず $ 6 $ 円で購入する。持っているクーポンは $ 1 $ 枚となる。 - $ 3 $ 種類目の商品をクーポンを使わず $ 2 $ 円で購入する。持っているクーポンは $ 2 $ 枚となる。 - $ 3 $ 種類目の商品をクーポンを使わず $ 2 $ 円で購入する。持っているクーポンは $ 3 $ 枚となる。 - $ 1 $ 種類目の商品をクーポンを使って $ 6 $ 円で購入する。持っているクーポンは $ 2 $ 枚となる。 - $ 4 $ 種類目の商品をクーポンを使って $ 3 $ 円で購入する。持っているクーポンは $ 1 $ 枚となる。 - $ 5 $ 種類目の商品をクーポンを使って $ 4 $ 円で購入する。持っているクーポンは $ 0 $ 枚となる。 $ 23 $ 円未満で全ての商品を $ 1 $ 回以上購入することはできないので、 $ 1 $ 行目には $ 23 $ を出力してください。 ### Constraints - $ 1\le T\le 2\times 10^5 $ - $ 1\le N\le 2\times 10^5 $ - $ 1\le B_i < A_i \le 10^9 $ - 全てのテストケースにおける $ N $ の総和は $ 2\times 10^5 $ 以下 - 入力される値は全て整数