COCI '09 Contest 1 #4 Mali

View as PDF

Submit solution


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

Problem type

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 a_1, a_2, \dots, a_n and b_1, b_2, \dots, 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 Specification

The first line of input contains a single integer N (1 \le N \le 10^5), number of rounds. The next N lines contain two integers A and B (1 \le A, B \le 100), numbers given by Slavko in that round.

Output Specification

The output consists of N 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

There are no comments at the moment.