Mirko and Slavko are playing a new game. Again. Slavko starts each round by giving Mirko two numbers and
, both smaller than
. Mirko then has to solve the following task for Slavko: how to pair all given
numbers with all given
numbers so that the maximal sum of such pairs is as small as possible.
In other words, if during previous rounds Slavko gave numbers and
, determine
pairings
such that each number in
sequence is used in exactly one pairing, and each number in
sequence is used in exactly one pairing and the maximum of all sums
is minimal.
Input Specification
The first line of input contains a single integer
, number of rounds. The next
lines contain two integers
and
, numbers given by Slavko in that round.
Output Specification
The output consists of lines, one for each round. Each line should contain the smallest maximal sum for that round.
Sample Input 1
3
2 8
3 1
1 4
Sample Output 1
10
10
9
Sample Input 2
3
1 1
2 2
3 3
Sample Output 2
2
3
4
Comments