← 返回题目列表

Codeforces · 983/C

C. 电梯

中文机器翻译题面 查看原题

你在一个大办公室工作。这是一栋 9 层楼的建筑,配有电梯,最多可容纳 4 人。您有责任管理这台电梯。

今天你迟到了,所以有些楼层已经有人排队了。对于每个人,您都知道他当前所在的楼层以及他想要到达的楼层。此外,您还知道人们进入电梯的顺序。

根据公司规定,如果一名员工比另一名员工先到电梯,他也必须先进入电梯(即使这些员工住在不同楼层)。请注意,员工可以按任意顺序离开电梯。

电梯有两个命令:

- 向上或向下一层。移动需要1秒。
- 打开当前楼层的门。在此操作过程中,所有到达目的地的员工均走出电梯。然后,在不违反公司规定且电梯内有足够空间的情况下,该楼层所有员工按照排队顺序进入电梯。每个员工进出电梯的时间为 1 秒。

电梯最初是空的,位于 1 楼。

您想知道将所有员工运送到目的地所需的最短时间是多少。电梯无需返回1层。

输入

第一行包含一个整数 n (1 ≤ n ≤ 2000) — 员工数量。

接下来 n 行的第 i 行包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ 9, ai ≠ bi) - 员工最初所在的楼层以及他想要到达的楼层。

员工按照到达电梯的顺序给出。

输出

打印一个整数——可能的最短时间(以秒为单位)。

示例

输入 #1

2
3 5
5 3

输出 #1

10

输入 #2

2
5 3
3 5

输出 #2

12

注意

第一个样本的解释 t = 0 t = 2 t = 3 t = 5 t = 6 t = 7 t = 9 t = 10