410280: GYM103999 I Dacians vs Samurai

As many of you might know, during the golden age of romanian television, one of the most beloved channels was named OTV.

One of the reasons for its popularity were the polls where the spectators voted for one of two options. Maybe the most popular poll was the one asking who would win in a fight between the dacians and the samurai.

After years and years, the OTV founder, DD, is back with his new project: DD Home Cinema. In order to regain his old level of fame he wants to please the nostalgics by bringing back the famous poll, but with a modern twist!

DD gives his spectators two integer sequences $$$A$$$ (the strenghts of the dacians) and $$$B$$$ (the strengths of the samurai) and wants another sequence $$$C$$$ of the same length, where $$$C_i \in \{A_i, B_i\}$$$ (either the $$$i$$$-th dacian or the $$$i$$$-th samurai). Because such a large sequence would not fit well on a tv display, he asks for his spectators only for the smallest difference in strength of such a sequence.

Formally, the spectators are asked for the minimum value of $$$max(C) - min(C)$$$ among all possible sequences $$$C$$$.

The first line will contain a single integer $$$N \leq 10^5$$$ - the length of the arrays $$$A$$$ and $$$B$$$.

The following $$$N$$$ lines will each contain 2 integers, $$$A_i, B_i \leq 10^9$$$, the values that form the sequences $$$A$$$ and $$$B$$$

The only line will contain a single integer - the minimum value of said expression.

• for 5 points, it is guaranteed that $$$N \leq 2$$$
• for another 15 points, it is guaranteed that $$$N \leq 20$$$
• for another 20 points, it is guaranteed that $$$N \leq 5000$$$
• for the last 60 points, we have $$$N \leq 10^5$$$

5
3 4
1 2
6 7
5 1
8 3

4

The minimum value is 4, and it can be obtain by choosing $$$C_1=A_1, C_2=B_2 , C_3=A_3 , C_4=A_4 , C_5 = B_5$$$.