AT_abc474_e.One Time Coupon

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.

某家商店出售 $N$ 种商品。每种商品均可购买任意多次。

第 $i$ 种商品（$1\le i\le N$）可通过以下两种方式购买：

• 不使用优惠券，以 $A_i$ 日元的价格购买，并获得一张优惠券；
• 使用一张优惠券，以 $B_i$ 日元的价格购买。

初始时，你没有优惠券。

求至少购买每种商品一次所需的最少金额。

你将得到 $T$ 组测试用例，请对每组用例求解。

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$

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

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

Output the answers for the test cases in order, separated by newlines.

按顺序输出测试用例的答案，答案之间用换行符分隔。

Sample 1 Explanation:
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.

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.

样例 1 解释：
考虑第一个测试用例。

例如，通过以下操作，可以以 23 日元的价格购买每种商品至少一次：

• 不使用优惠券，以 6 日元购买第二种商品。此时拥有 1 张优惠券。
• 不使用优惠券，以 2 日元购买第三种商品。此时拥有 2 张优惠券。
• 不使用优惠券，以 2 日元再次购买第三种商品。此时拥有 3 张优惠券。
• 使用 1 张优惠券，以 6 日元购买第一种商品。此时拥有 2 张优惠券。
• 使用 1 张优惠券，以 3 日元购买第四种商品。此时拥有 1 张优惠券。
• 使用 1 张优惠券，以 4 日元购买第五种商品。此时拥有 0 张优惠券。

无法以低于 23 日元的价格购买每种商品至少一次，因此在第一行输出 $23$。

约束条件

• $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$。
• 所有输入值均为整数。