Elevator
Contest: Codeforces Round 483 (Div. 1) [Thanks, Botan Investments and Victor Shaburov!]
Difficulty rating: 2400
Tags: dp, graphs, shortest paths

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.

Input format:
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 ai and bi (1 ≤ ai, bi ≤ 9, ai ≠ bi) — 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.

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Explaination for the first sample  t = 0 t = 2 t = 3 t = 5 t = 6 t = 7 t = 9 t = 10

Example input:
2
3 5
5 3

Example output:
10

Example input:
2
5 3
3 5

Example output:
12

Editorial:
This problem is inspired by living in the house of 9 floors with the elevator, which can accommodate up to 4 people. What a surprise!
We have a strict order. So let's make dp[i][state] =  minimal possible time, where i means that first i employees already came in the elevator (and possibly came out).
So, what is a state? Let's store something what will allow us to determine the state. For this purpose we want to know the floor, where the elevator currently is, and number of people, who want to reach each floor. So, it's 10 integers. Let's estimate the number of states: floor takes 9 values, state can take $${ \binom { 9 } { 4 } } + { \binom { 9 } { 3 } } + { \binom { 9 } { 2 } } + { \binom { 9 } { 1 } } + { \binom { 9 } { 0 } } = 2 5 6$$ (Wow!). Also let's notice, that we don't want to visit floor of nobody in the elevator don't want to go there and the next person isn't on that floor. So we have not more than 5 interesting floors for each state. Let's say the total count of states is s = 5·256.
Now we've got two different solutions.
The fast one is we say we go from the floor a[i] to the floor a[i + 1] and iterate over the persons who we let come in on the way.
The slow one is to run Dijkstra for each i: from state we can go to the floor and let somebody come out or go to the floor a[i + 1]. Now, when we calculated answers for i - 1, we can calculate dp[i][state] = 1 + dp[i - 1][state], if state has floor equals to ai and there are no more than 3 people inside.
The answer will be in dp[n][floor = j & elevator is empty] for $$j \in [1,9]$$.
Asymptotics is O(n·s) or O(n·s·log(s))
Solution