27206번 - Relay 서브태스크다국어

There are $N$ members in the track club of JOI High School, numbered from $1$ to $N$. For the member $i$ ($1 ≤ i ≤ N$), the time of the 100 m sprint is $A_i$ msec, and the ability of controlling the baton is $B_i$.

The track club will participate in a national contest for the 300 m relay. Three members will run in the 300 m relay. Each member will run for 100 m. A runner will pass the baton to the next runner. Precisely, if the first runner is the member $i$ ($1 ≤ i ≤ N$), the second runner is the member $j$ ($1 ≤ j ≤ N$), and the third runner is the member $k$ ($1 ≤ k ≤ N$), then the three members will run the relay in the following steps.

1. The member $i$ runs for 100 m with a baton. It takes $A_i$ msec.
2. The member $i$ gives a baton to the member $j$. It takes $\max{(B_i , B_j)}$ msec.
3. The member $j$ runs for 100 m with a baton. It takes $A_j$ msec.
4. The member $j$ gives a baton to the member $k$. It takes $\max{(B_j , B_k)}$ msec.
5. The member $k$ runs for 100 m with a baton. It takes $A_k$ msec.

Therefore, the record for the 300 m relay is $A_i + \max{(B_i , B_j)} + A_j + \max{(B_j , B_k)} + A_k$ msec. Here $\max{(x, y)}$ is the largest value of $x$ and $y$. Since you are the coach of the track club, you want to choose three distinct members for the relay and decide the order of the runners so that the record becomes minimum.

Write a program which, given information of the $N$ members of the track club, calculates the minimum possible record of the 300 m relay.

Read the following data from the standard input. Given values are all integers.

$N$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

Write one line to the standard output. The output should contain an integer which is the minimum possible record of the 300 m relay counted by msec.

• $3 ≤ N ≤ 200\,000$.
• $1 ≤ A_i ≤ 100\,000\,000 (= 10^8)$ ($1 ≤ i ≤ N$).
• $1 ≤ B_i ≤ 100\,000\,000 (= 10^8)$ ($1 ≤ i ≤ N$).