旅行商高桥

题目描述

数轴上有编号为 $1$ 到 $N$ 的 $N$ 个球。

球 $i$ 位于坐标 $X_i$。

每个球都有用 $1$ 以上 $N$ 以下的整数表示的颜色，球 $i$ 的颜色用整数 $C_i$ 表示。

现在位于坐标 $0$ 的你，以每秒 $1$ 的速度在数轴上移动，收集所有球之后再回到坐标 $0$。

此时，把表示球的颜色的整数按收集顺序排列后，需要构成非递减（广文单调递增）序列。

要收集某个球，需要移动到与该球相同的坐标，但即使可以收集某个球，也不一定必须立即收集。

求从坐标 $0$ 出发，到收集完所有球并回到坐标 $0$ 为止所需的最短时间。

输入格式

输入按以下格式从标准输入给出：

$N$
$X_1$ $C_1$
$X_2$ $C_2$
$X_3$ $C_3$
$\hspace{15pt} \vdots$
$X_N$ $C_N$

输出格式

输出答案 [秒]。

样例

5
2 2
3 1
1 3
4 2
5 3

12

按如下方式行动是最优的：

• 花 $3$ 秒移动到坐标 $3$，收集球 $2$
• 花 $1$ 秒移动到坐标 $2$，收集球 $1$
• 花 $2$ 秒移动到坐标 $4$，收集球 $4$
• 花 $1$ 秒移动到坐标 $5$，收集球 $5$
• 花 $4$ 秒移动到坐标 $1$，收集球 $3$
• 花 $1$ 秒回到坐标 $0$

把表示球颜色的整数按收集顺序排列得到 $1, 2, 2, 3, 3$，是非递减的。

9
5 5
-4 4
4 3
6 3
-5 5
-3 2
2 2
3 3
1 4

38

数据范围

• $1 \le N \le 2 \times 10^5$
• $|X_i| \le 10^9$
• $X_i \neq X_j\ (i \neq j)$
• $X_i \neq 0$
• $1 \le C_i \le N$
• 输入中的值均为整数