题目描述

到了学期末，在幼儿园工作的小爱要为自己班级的小朋友分发糖果。小爱的班上共有$n$名小朋友，第$i$位小朋友对糖果的喜爱程度为$a_i$，他在本学期的表现评分为$b_i$。小爱分配糖果的方法如下：

1. 以某个顺序安排这$n$位小朋友排成一排，小爱从头到尾逐一分配糖果。

2. 队伍中的第$i$位小朋友至少获得的糖果数量为前$i$位小朋友对糖果的喜爱程度之和。

3. 由于第$i$位小朋友可以看见第$i -1$位小朋友获得的糖果数量，为了不让第$i$位小朋友觉得不公平，小爱保证第$i$位小朋友获得的糖果不少于第$i - 1$位小朋友。

4. 在为第$i$位小朋友分配完糖果后，小爱将额外再奖励第$i$位小朋友数量为$b_i$的糖果。

我们设第$i$位小朋友获得的糖果数量为$c_i$，形式化地讲：

$$c_i = \begin{cases} a_1+b_1, & i=1 \\ \max\{c_{i-1}, \sum_{j=1}^i a_j \} + b_i & 2\le i \le n \end{cases} $$

由于预算有限，小爱希望你能帮她安排这$n$位小朋友的顺序，使得获得糖果最多的小朋友，所获得的糖果数量尽可能少。

输入格式

第一行包含一个正整数$T$，表示测试数据的组数。

接下来描述这$T$组测试数据，每组数组的第一行包含一个正整数$n$，表示小爱班上小朋友的数量。

每组数据接下来$n$行中，每行两个正整数，分别为$a_i$和$b_i$，含义如问题描述中所述。

输出格式

共$T$行，每行包含一个整数，表示被分配到最多糖果的那位小朋友最少获得的糖果数量。

1 
3 
4 1
2 2 
1 2

8

样例解释 1

按 3，2，1 顺序领取时，分到最多糖果的那位小朋友获得的糖果数量为8

数据范围

对于 $10\%$ 的数据：$1 \leq n \leq 2$，且$T=1$ 对于 $40\%$ 的数据：$1 \leq n \leq 16$，且$T\leq5$ 对于 $60\%$ 的数据：$1 \leq n \leq 5\times10^3$ 对于 $70\%$ 的数据：$1 \leq n \leq 10^4$ 对于 $100\%$ 的数据：$1 \leq n \leq 5\times10^4$，且$T \leq 10$