## COCI '09 Contest 1 #4 Mali

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 32M

Problem type

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