你在一个大办公室工作。这是一栋 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