/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 450 点
問題文
ある店では N 種類の商品が売られています。各商品は何回でも購入することができます。
i 種類目 (1\le i\le N) の商品は以下の 2 通りの方法で買うことができます：
- クーポンを使わずに A_i 円で購入し、クーポンを 1 枚もらう。
- クーポンを 1 枚使い、B_i 円で購入する。
最初、あなたはクーポンを 1 枚も持っていません。
全ての商品を 1 回以上購入するために必要な金額の最小値を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 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 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
入力例 1
3 5 11 6 6 5 2 1 8 3 7 4 4 5 1 5 2 5 3 5 4 6 24 13 24 2 50 12 35 25 28 26 10 1
出力例 1
23 13 100
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 を出力してください。
Score : 450 points
Problem Statement
A certain shop sells N types of products. Each product can be purchased any number of times.
The i-th type of product (1\le i\le N) can be bought in the following two ways:
- Buy it for A_i yen without using a coupon, and receive one coupon.
- Use one coupon and buy it for B_i yen.
Initially, you have no coupons.
Find the minimum amount of money required to buy every product at least once.
You are given T test cases; solve each of them.
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
- The sum of N over all test cases is at most 2\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Output the answers for the test cases in order, separated by newlines.
Sample Input 1
3 5 11 6 6 5 2 1 8 3 7 4 4 5 1 5 2 5 3 5 4 6 24 13 24 2 50 12 35 25 28 26 10 1
Sample Output 1
23 13 100
Consider the first test case.
For example, by acting as follows, you can buy every product at least once for 23 yen:
- Buy the second type of product for 6 yen without using a coupon. You now have 1 coupon.
- Buy the third type of product for 2 yen without using a coupon. You now have 2 coupons.
- Buy the third type of product for 2 yen without using a coupon. You now have 3 coupons.
- Use a coupon to buy the first type of product for 6 yen. You now have 2 coupons.
- Use a coupon to buy the fourth type of product for 3 yen. You now have 1 coupon.
- Use a coupon to buy the fifth type of product for 4 yen. You now have 0 coupons.
It is impossible to buy every product at least once for less than 23 yen, so output 23 on the first line.