题目描述

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

第 $i$ 种商品 $(1 \le i \le N)$ 有下面两种购买方式：

• 不使用优惠券，花 $A_i$ 元购买，并获得 $1$ 张优惠券；
• 使用 $1$ 张优惠券，花 $B_i$ 元购买。

最初你一张优惠券都没有。

请求出把每种商品都至少买一次所需金额的最小值。

输入包含 $T$ 组测试数据，请对每组分别求解。

输入格式

T
case_1
case_2
...
case_T

每组测试数据的格式为：

N
A_1 B_1
A_2 B_2
...
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 说明

考虑第 $1$ 组数据。按下面的方式行动即可用 $23$ 元买齐所有商品：

• 不用券花 $6$ 元买第 $2$ 种商品，持券数变为 $1$；
• 不用券花 $2$ 元买第 $3$ 种商品，持券数变为 $2$；
• 不用券再花 $2$ 元买一次第 $3$ 种商品，持券数变为 $3$；
• 用券花 $6$ 元买第 $1$ 种商品，持券数变为 $2$；
• 用券花 $3$ 元买第 $4$ 种商品，持券数变为 $1$；
• 用券花 $4$ 元买第 $5$ 种商品，持券数变为 $0$。

注意其中第 $3$ 种商品被买了两次——多买一次纯粹是为了多攒一张券。这说明「为了攒券而额外购买」有时是划算的。

输入示例 2

2
1
10 1
3
100 1
100 1
100 1

输出示例 2

10
201

示例 2 说明

第 $1$ 组只有一种商品，开局没有券，只能不用券买，答案就是 $A_1 = 10$。

第 $2$ 组三种商品完全相同。最优做法是：不用券买两次（$100 + 100$），攒下 $2$ 张券，再用券买最后一种（$1$），共 $201$。若三种都不用券要 $300$；若想用券买两种，就得先额外买一次凑券，反而更贵。这组数据用来检验额外购买张数的取舍。

输入示例 3

1
2
1000000000 999999999
1000000000 999999999

输出示例 3

1999999999

示例 3 说明

$A_i$ 取到上限 $10^9$，两种商品各买一次的总额接近 $2 \times 10^9$，已经超出 $32$ 位整数范围。这组数据用来检验是否使用了 long long。

约束条件

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