Elevator

题意翻译

## 题意 一个$9$层的楼有一个可以容纳$4$个人的电梯,你要管理这个电梯。 现在各层楼上有一些在排队的人,你知道他们在哪层要到哪层去。你也知道到电梯门口的顺序。根据公司的规定,如果一个人比其他人早到。他也必须先进电梯(无论楼层,只凭时间)。注意人们可以随时离开电梯。 电梯有两个命令: * 上楼或者下楼, 代价为1 * 打开当前楼层的门,所有到目的地的人会从电梯里出来,当前楼层排队的人会在**不违反规定的情况下**一个一个进(在电梯还有空间的情况下)(这不是天朝的电梯,不能超员)每个人用1s时间来出入电梯。 最初电梯是空的,在1楼。你需要求出最少用多长时间来吧所有人送回到目的地。最后电梯可以停在任意位置 ## 输入输出格式: ### 输入格式 * 第一行一个整数 : 人数量 $N$ * 之后n行:第i行包含两个整数$A_i$,$B_i$ -- $A_i$表示最初楼层,$B_i$表示目的楼层。到达电梯门口的顺序按输入顺序排序 ### 输出格式 * 一个整数表示以秒为单位的最小时间 感谢@ToBiChi 提供翻译和@communist 提供的建议

题目描述

You work in a big office. It is a $ 9 $ floor building with an elevator that can accommodate up to $ 4 $ people. It is your responsibility to manage this elevator. Today you are late, so there are queues on some floors already. For each person you know the floor where he currently is and the floor he wants to reach. Also, you know the order in which people came to the elevator. According to the company's rules, if an employee comes to the elevator earlier than another one, he has to enter the elevator earlier too (even if these employees stay on different floors). Note that the employees are allowed to leave the elevator in arbitrary order. The elevator has two commands: - Go up or down one floor. The movement takes $ 1 $ second. - Open the doors on the current floor. During this operation all the employees who have reached their destination get out of the elevator. Then all the employees on the floor get in the elevator in the order they are queued up while it doesn't contradict the company's rules and there is enough space in the elevator. Each employee spends $ 1 $ second to get inside and outside the elevator. Initially the elevator is empty and is located on the floor $ 1 $ . You are interested what is the minimum possible time you need to spend to deliver all the employees to their destination. It is not necessary to return the elevator to the floor $ 1 $ .

输入输出格式

输入格式


The first line contains an integer $ n $ ( $ 1<=n<=2000 $ ) — the number of employees. The $ i $ -th of the next $ n $ lines contains two integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i},b_{i}<=9 $ , $ a_{i}≠b_{i} $ ) — the floor on which an employee initially is, and the floor he wants to reach. The employees are given in the order they came to the elevator.

输出格式


Print a single integer — the minimal possible time in seconds.

输入输出样例

输入样例 #1

2
3 5
5 3

输出样例 #1

10

输入样例 #2

2
5 3
3 5

输出样例 #2

12

说明

Explaination for the first sample ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF983C/42ae00c4e996365f20671191db4d171f557d952f.png) $ t=0 $ ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF983C/b2ae1c781d5e41af1a63a1db1ebf6bd900263fcd.png) $ t=2 $ ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF983C/8987100fe621ece7aac6b15186332843eb828c37.png) $ t=3 $ ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF983C/3c69dce4611baf4e5023871e23d3cb8dd2c3c5ec.png) $ t=5 $ ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF983C/9ede429dc712ced76dce854f2b6342387838877d.png) $ t=6 $ ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF983C/1fa6644530dbfd518f3c2d592f380b5a8de35aca.png) $ t=7 $ ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF983C/baae1d495f59bd6229dc09b23773aef109cdf42b.png) $ t=9 $ ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF983C/83a570b88fddc65ced5cd02c41a644b496f2986d.png) $ t=10 $