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.

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

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.

• Source: AtCoder ABC 474 E