JOI 高中田径俱乐部共有 $N$ 名成员，编号为 $1$ 到 $N$。对于成员 $i$ ($1 \le i \le N$)，其 $100$ 米短跑用时为 $A_i$ 毫秒，接力棒控制能力为 $B_i$。

田径俱乐部将参加一场 $300$ 米接力赛。接力赛由三名成员参加，每人跑 $100$ 米。选手之间需要传递接力棒。具体来说，如果第一棒是成员 $i$ ($1 \le i \le N$)，第二棒是成员 $j$ ($1 \le j \le N$)，第三棒是成员 $k$ ($1 \le k \le N$)，则这三名成员按以下步骤完成接力：

1. 成员 $i$ 持棒跑 $100$ 米，耗时 $A_i$ 毫秒。
2. 成员 $i$ 将接力棒交给成员 $j$，耗时 $\max(B_i, B_j)$ 毫秒。
3. 成员 $j$ 持棒跑 $100$ 米，耗时 $A_j$ 毫秒。
4. 成员 $j$ 将接力棒交给成员 $k$，耗时 $\max(B_j, B_k)$ 毫秒。
5. 成员 $k$ 持棒跑 $100$ 米，耗时 $A_k$ 毫秒。

因此，$300$ 米接力赛的总成绩为 $A_i + \max(B_i, B_j) + A_j + \max(B_j, B_k) + A_k$ 毫秒。其中 $\max(x, y)$ 表示 $x$ 和 $y$ 中的较大值。作为田径俱乐部的教练，你需要选择三名不同的成员参加接力，并决定他们的出场顺序，使得总成绩最小。

请编写一个程序，根据 $N$ 名成员的信息，计算 $300$ 米接力赛的最小可能成绩。

输入格式

从标准输入读取以下数据。给定值均为整数。

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

输出一行到标准输出，包含一个整数，表示 $300$ 米接力赛的最小可能成绩（单位：毫秒）。

数据范围

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

子任务

1. ($25$ 分) $N \le 100$
2. ($33$ 分) $N \le 3\,000$
3. ($10$ 分) $A_1 = A_2 = \dots = A_N$
4. ($32$ 分) 无附加限制

样例

样例输入 1

4
1070 90
1080 70
1050 60
1020 100

样例输出 1

3320

说明 1

如果第一棒是成员 $4$，第二棒是成员 $3$，第三棒是成员 $2$，则接力赛步骤 $1, 2, 3, 4, 5$ 的耗时分别为 $1020, 100, 1050, 70, 1080$ 毫秒。因此，$300$ 米接力赛的总成绩为 $1020 + 100 + 1050 + 70 + 1080 = 3320$ 毫秒。这是最小可能成绩，故输出 $3320$。

样例输入 2

5
1000 28
1000 14
1000 21
1000 20
1000 14

样例输出 2

3034

样例输入 3

9
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3
2 3

样例输出 3

13