You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

数字游戏

题目描述

小容和小雅在玩数字游戏。游戏规则是这样的:最开始有两空的数列 A和 B，第i次小雅会给数列 A和B分别增加一组数 $A_i$，$B_i$，而小容可以将A和B 以任意方式重新排序，使得所有$A_i+B_i$的最大值最小。请你帮小容在每一次小雅给出两个新的数之后，求出$A_i+B_i$最大值的最小值。

输入格式

第一行包括1个正整数，表示小T给出数字的次数

接下来N行，第i+1行包括2个正整数A， B，表示每一次小T给出的数对

输出格式

输出包括N行，对于每一次小雅给出的数字，求出所求排列中对应A和B之和的最大值的最小值.

样例 #1

样例输入 #1

3
2 8
3 1
1 4

样例输出 #1

10
10
9

样例 #2

样例输入 #2

3
1 1
2 2
3 3

样例输出 #2

2
3
4

提示

第一组样例解释: 第一次询问:$A=(2)，B=(8)，Min(A_i+B_i)=2+8=10$

第二次询问:$A=(2,3)，B=(8,1)，Min(A_i+B_i)=2+8=10$;

第三次询问: A=(1,2,3)，B=(8,1,4}，Min(A_i+B_i}=1+8=9;

数据范围

对于$50\%$的数据，有$N \leq 200$;

对于$100\%$的数据，有$1\leq N \leq 100000,1\leq A，B \leq 200$。