엘리베이터

당신은 큰 사무실에서 일한다. 이곳은 최대 4명까지 탈 수 있는 엘리베이터가 있는 9층 건물이다. 이 엘리베이터를 관리하는 것은 당신의 책임이다.

오늘 당신은 늦었기 때문에 일부 층에는 이미 대기열이 생겨 있다. 각 사람이 현재 있는 층과 도착하려는 층을 알고 있다. 또한 사람들이 엘리베이터에 도착한 순서도 알고 있다.

회사의 규칙에 따르면 어떤 직원이 다른 직원보다 엘리베이터에 먼저 도착했다면, 그 직원은 엘리베이터에도 먼저 타야 한다. 두 직원이 서로 다른 층에 있더라도 마찬가지이다. 직원들은 임의의 순서로 엘리베이터에서 내릴 수 있다는 점에 유의한다.

엘리베이터에는 두 가지 명령이 있다.

• Go 한 층 위나 아래로 이동한다. 이동에는 1초가 걸린다.
• 현재 층에서 문을 연다. 이 작업 중에 목적지에 도착한 모든 직원이 엘리베이터에서 내린다. 그런 다음 회사의 규칙에 t 위배되지 않고 엘리베이터에 충분한 공간이 있는 동안, 해당 층의 모든 직원이 대기열 순서대로 엘리베이터에 탄다. 각 직원이 엘리베이터에 타거나 내리는 데에는 1초가 걸린다.

처음에 엘리베이터는 비어 있으며 1층에 있다.

모든 직원을 목적지까지 데려다주는 데 필요한 최소 시간을 구하려고 한다. 엘리베이터를 1층으로 되돌릴 필요는 없다.

첫째 줄에 직원 수를 나타내는 정수 n가 주어진다 (1 ≤ n ≤ 2000).

이어지는 n개 줄 중 i-th 줄에는 정수 ai와 bi가 주어진다 (1 ≤ ai, bi ≤ 9, ai ≠ bi). 이는 각각 직원이 처음에 있는 층과 그 직원이 도착하려는 층이다.

직원들은 엘리베이터에 도착한 순서대로 주어진다.

가능한 최소 시간을 초 단위의 정수 하나로 출력한다.

첫 번째 예제에 대한 설명 t = 0

t = 2

t = 3

t = 5

t = 6

t = 7

t = 9

t = 10