COCI '09 Contest 1 #4 Mali

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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, a_3, \dots, a_n and b_1, b_2, b_3, \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

2 8
3 1
1 4

Sample Output 1


Sample Input 2

1 1
2 2
3 3

Sample Output 2



There are no comments at the moment.