레이팅 미적용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 the rounds so far Slavko gave the numbers \(a_1, a_2, a_3, \ldots, a_n\) and \(b_1, b_2, b_3, \ldots, b_n\), determine \(n\) pairings \((a_i, b_j)\) such that each number in the \(A\) sequence is used in exactly one pairing, each number in the \(B\) sequence is used in exactly one pairing, and the maximum of all sums \(a_i + b_j\) is minimal.
The first line of input contains a single integer \(N\) (\(1 \le N \le 100\,000\)), the number of rounds.
Each of the next \(N\) lines contains two integers \(A\) and \(B\) (\(1 \le A, B \le 100\)), the numbers given by Slavko in that round.
Output consists of \(N\) lines, one for each round. Each line should contain the smallest maximal sum for that round (considering all numbers given up to and including that round).
Scoring: Test cases worth \(50\%\) of total points have \(N \le 200\).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 50점 | \(N \le 200\) |
Subtask 2 | 50점 | No additional constraints (\(N \le 100\,000\)). |
3
2 8
3 1
1 410
10
93
1 1
2 2
3 32
3
4