P7542 [COCI 2009/2010 #1] MALI

Mirko and Slavko are playing a game. The game has a total of $N$ rounds. In round $k$, Slavko gives two integers $A_k$ and $B_k$. Please help Mirko solve the following problem: In the first $k$ rounds, Slavko has given the numbers $A_1, A_2, ..., A_k$ and $B_1, B_2, ..., B_k$. Pair these numbers into $k$ pairs $(A_i, B_j)$ ($1 \le i, j \le k$), such that every number in sequence $A$ and every number in sequence $B$ appears **exactly once** among these pairs, and the **maximum** value among the **sums** of all pairs ($A_i + B_j$) is minimized.

The first line contains an integer $N$, indicating the number of rounds in the game. The next $N$ lines each contain two integers $A_i, B_i$, indicating the two numbers Slavko gives in round $i$.

Output $N$ lines. The $i$-th line should be the minimum possible maximum pair sum after round $i$.

#### Constraints For $50\%$ of the testdata, $1 \le N \le 200$. For $100\%$ of the testdata, $1 \le N \le 10^5$, $1 \le A_i, B_i \le 100$. #### Notes The scoring of this problem follows the original COCI problem settings, with a full score of $100$. Translated from [**COCI2009-2010 CONTEST #1**](https://hsin.hr/coci/archive/2009_2010/contest1_tasks.pdf) _**T4 MALI**_. Translated by ChatGPT 5