题目描述

新学期开始啦！少不了的一件事自然就是分配同桌

面条老师的班级里有 $n$ 个男生和 $n$ 个女生，男女生坐在一起，正好分成 $n$ 对同桌

而为了促进同学们的学习进步，面条老师决定根据每个同学的成绩情况进行分配同桌

首先面条老师收集了每个同学的平均成绩，第 $i$ 个男生的成绩为 $b_i$，第 i 个女生的成绩为 $g_i$

如果由第 $i$ 个男生和第 $j$ 个女生组成同桌，那么这一对同桌的成绩为 $b_i + g_j$

当分配完 $n$ 对同桌以后，成绩最高的那一对同桌的成绩将代表这一次同桌分配方案的分配度

面条老师认为，分配度越小，这一组分配方案越好，现在面条老师想知道，最小的分配度是多少？

输入格式

第一行一个整数 $n$ 表示男女生人数。

接下来每行包含两个整数 $b_i$ 和 $g_i$ 分别表示第 $i$ 个男生和第 $i$ 个女生的成绩。

输出格式

输出共 $n$ 行，请计算每新增一对男女生时的最小分配度。

3
2 8
3 1
1 4

10
10
9

样例解释

男生 $2$，女生 $8$，分配方案为 $2+8=10$

男生 $2,3$，女生 $8,1$，分配方案为 $2+8=10,3+1=4$,分配度为 $max(10,4)=10$

男生 $2,3,1$，女生 $8,1,4$，其中一种分配度最小的方案为 $1+8=9,3+4=7,2+1=3$ 此时分配度是 $max(9,3,7)=9$

数据规模与约定

对于 $20\%$ 的数据，$1\leq n\leq 5,1\leq a_i,b_i\leq 10$；

对于 $40\%$ 的数据，$1\leq n\leq 100,1\leq a_i,b_i\leq 100$；

对于 $70\%$ 的数据，$1\leq n\leq 10^3,1\leq a_i,b_i\leq 100$；

对于 $100\%$ 的数据，$1\leq n\leq 10^5,1\leq a_i,b_i\leq 100$。