### 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_{1}, a_{2}, a_{3} .... a_{n} and b_{1}, b_{2}, b_{3} ... 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

## Input3 2 8 3 1 1 4 ## Output10 10 9 |
## Input3 1 1 2 2 3 3 ## Output2 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)

It's quiet in here...