AT_abc474_e [ABC474E] 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.

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 the answers for the test cases in order, separated by newlines.

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