题目描述

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

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

• 不使用优惠券，支付 $A_i$ 日元购买，并获得一张优惠券；
• 使用一张优惠券，支付 $B_i$ 日元购买。

初始时，你一张优惠券也没有。

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

给定 $T$ 组测试数据，请分别求解每组数据。

输入格式

输入按以下格式从标准输入读入：

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

输出格式

按顺序输出每组测试数据的答案，每行一个，以换行分隔。

数据范围

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

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

考虑第一组测试数据。

例如，按如下方式操作，可以用 $23$ 日元买下每种商品至少一次：

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

无法用少于 $23$ 日元就买下每种商品至少一次，因此在第一行输出 $23$。

• 来源：AtCoder ABC 474 E

子任务设置

• 子任务 1（30 分）：$T\le 10$，$N\le 8$，$A_i\le 100$。
• 子任务 2（30 分）：所有测试数据的 $N$ 之和不超过 $2000$。
• 子任务 3（40 分）：无特殊限制。