问题 E: 收集

内存限制:1024 MB 时间限制:2.000 S
评测方式:文本比较 命题人:
提交:10 解决:2

题目描述

给定数轴上分布着 N 个球,分别称为 Ball 1 到 Ball N。每个球都位于坐标 $X_i$ 处,其中 $i$ 为球的编号。每个球都有一个颜色标识,用整数 ID 表示,ID 的取值范围为 1 到 N(包括 1 和 N)。第 $i$ 个球的颜色 ID 为 $C_i$。
你目前位于坐标 0,并以每秒移动一个单位的速度沿着数轴收集球,然后返回到坐标 0。在收集球的过程中,你必须按照球的 ID 非递减的顺序进行收集。也就是说,你必须先收集 ID 最小的球,然后依次按照递增的顺序收集球。当你位于某个球的坐标时,你可以选择是否收集该球。
请找出从坐标 0 开始,收集所有球,并返回到坐标 0 所需的最短时间。

输入

$1 \leq N \leq 2 \times 10^5$
$|X_i| \leq 10^9$ for all $i$
$X_i \neq X_j$ for $i \neq j$
$X_i \neq 0$
$1 \leq C_i \leq N$
所有输入值都是整数。

输出

答案

样例输入 复制

5
2 2
3 1
1 3
4 2
5 3

样例输出 复制

12