Вы работаете в большом офисе, которое представляет из себя 9-этажное здание с одним лифтом, вмещающим 4 человека. В ваши обязанности входит управлять этим лифтом.
Сегодня вы опоздали на работу, и у лифта уже выстроились очереди на разных этажах. Про каждого человека известно, на каком этаже он сейчас находится и на какой этаж хочет попасть. Также известен порядок, в котором люди подходили к лифту.
По правилам компании, если сотрудник подошел к лифту раньше другого, то он должен оказаться внутри лифта раньше (даже если они находятся на разных этажах). Выходить сотрудники могут в любом порядке.
У лифта есть две команды:
- Проехать на один этаж вверх/вниз. На перемещение тратится 1 секунда.
- Открыть двери на этаже. После этого все сотрудники, которым нужно выйти на этом этаже выйдут из лифта. После этого сотрудники, находящиеся на этаже, начнут заходить в лифт в порядке очереди, пока это не противоречит правилам и в лифте достаточно места. Люди заходят и выходят последовательно, каждый тратит 1 секунду на вход или выход.
Изначально лифт находится на 1 этаже.
Вам интересно, сколько нужно времени, чтобы доставить всех сотрудников на нужные этажи. Не обязательно возвращать лифт на 1 этаж.
В первой строке дано целое число n (1 ≤ n ≤ 2000) — число сотрудников в очереди.
i-я из следующих n строк содержит два целых числа ai и bi (1 ≤ ai, bi ≤ 9, ai ≠ bi) — этаж, на котором находится сотрудник, и этаж, на который он хочет попасть.
Сотрудники даны в порядке, в котором они подходили к лифту.
Выведите одно целое число — минимальное время в секундах.
2
3 5
5 3
10
2
5 3
3 5
12
t = 0
t = 2
t = 3
t = 5
t = 6
t = 7
t = 9
t = 10
