MALI
Mirko and Slavko are playing a new game. Again. Slavko starts each round by giving Mirko two numbers A and B, both smaller than 100. Mirko then has to solve the following task for Slavko: how to pair all given A numbers with all given B numbers so that the maximal sum of such pairs is as small as possible.
In other words, if during previous rounds Slavko gave numbers a1, a2, a3 .... an and b1, b2, b3 ... bn, determine n pairings (ai, bj) such that each number in A sequence is used in exactly one pairing, and each number in B sequence is used in exactly one pairing and the maximum of all sums ai + bj is minimal.
InputThe first line of input contains a single integer N (1 ≤ N ≤ 100000), number of rounds. Next N lines contain two integers A and B (1 ≤ A, B ≤ 100), numbers given by Slavko in that round.(Test cases worth 50% of total points have N ≤ 200.)
OutputOutput consists of N lines, one for each round. Each line should contain the smallest maximal sum for that round.
Input:
3
2 8
3 1
1 4
Output:
10
10
9Input:
3
1 1
2 2
3 3Output:
2
3
4Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.