COCI 2009/2010, Contest #1

Task 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 slove the following task for Slavko: how to pair all given A numbers with all given B numbes so that the maximal sum of such pairs is as small as possible.

In other words, if during previous rounds Slavko gave numbers a₁, a₂, a₃ .... a_n and b₁, b₂, b₃ ... b_n, determine n pairings (a_i, b_j) 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 a_i + b_j is minimal.

Input

The first line of input contains a single integer N (1 ≤ N ≤ 100 000), number of rounds.

Next N lines contain two integers A and B (1 ≤ A, B ≤ 100), numbers given by Slavko in that round.

Output

Output consists of N lines, one for each round. Each line should contain the smallest maximal sum for that round.

Scoring

Test cases worth 50% of total points have N ≤ 200.

Sample Tests

3
2 8
3 1
1 4

10
10
9

3
1 1
2 2
3 3

2
3
4

All Submissions
Best Solutions

Point Value: 10
Time Limit: 1.00s
Memory Limit: 32M
Added: Jul 03, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)