题目描述

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

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

1. 不使用优惠券，花费 $A_i$ 元购买，并在购买后获得一张优惠券。
2. 消耗一张优惠券，花费 $B_i$ 元购买。

最初，你没有任何优惠券。

请计算出每种商品至少购买一次所需的最少总花费。

本题包含 $T$ 个测试用例，请逐个求解。

输入格式

第一行包含一个正整数 $T$ —— 表示测试用例的数量。

对于每个测试用例，输入格式如下： 第一行包含一个正整数 $N$ —— 表示商品的种类数。 接下来 $N$ 行，每行包含两个正整数 $A_i$ 和 $B_i$ —— 分别表示第 $i$ 种商品在不使用优惠券和使用优惠券时的购买价格。

输出格式

对于每个测试用例，输出一行一个整数，表示买齐所有商品所需的最少花费。

样例输入 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

说明

样例解释

考虑第一个测试用例。你可以通过以下步骤，花费 $23$ 元买齐所有种类的商品：

1. 不使用优惠券花费 $6$ 元购买第 $2$ 种商品。此时你拥有 $1$ 张优惠券。
2. 不使用优惠券花费 $2$ 元购买第 $3$ 种商品。此时你拥有 $2$ 张优惠券。
3. 不使用优惠券花费 $2$ 元再次购买第 $3$ 种商品。此时你拥有 $3$ 张优惠券。
4. 消耗 $1$ 张优惠券花费 $6$ 元购买第 $1$ 种商品。此时你拥有 $2$ 张优惠券。
5. 消耗 $1$ 张优惠券花费 $3$ 元购买第 $4$ 种商品。此时你拥有 $1$ 张优惠券。
6. 消耗 $1$ 张优惠券花费 $4$ 元购买第 $5$ 种商品。此时你拥有 $0$ 张优惠券。

此时你已经至少购买了所有 $5$ 种商品一次，总花费为 $6+2+2+6+3+4=23$ 元。 由于无法以低于 $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$。
• 保证所有的输入数值均为整数。