Фурик и Рубик любят играть в компьютерные игры. Недавно Фурик нашел новую игру, которая очень заинтересовала Рубика. Игра состоит из n частей, причем для прохождения каждой части, возможно, требуется пройти некоторые другие. Известно, что игру можно пройти полностью, то есть нет циклических зависимостей между частями игры.
У Рубика есть 3 компьютера, на которых он может играть в эту игру. Все компьютеры находятся в разных домах и, как оказалось, каждую часть игры можно пройти только на одном из этих компьютеров. Пронумеруем компьютеры целыми числами от 1 до 3. Рубик может выполнять следующие действия:
- Пройти какую-то часть игры на каком-то компьютере. Рубик тратит на прохождение любой части на любом компьютере ровно 1 час.
- Переместиться от 1-го компьютера ко 2-му. На это действие Рубик тратит ровно 1 час.
- Переместиться от 1-го компьютера к 3-му. На это действие Рубик тратит ровно 2 часа.
- Переместиться от 2-го компьютера к 1-му. На это действие Рубик тратит ровно 2 часа.
- Переместиться от 2-го компьютера к 3-му. На это действие Рубик тратит ровно 1 час.
- Переместиться от 3-го компьютера к 1-му. На это действие Рубик тратит ровно 1 час.
- Переместиться от 3-го компьютера ко 2-му. На это действие Рубик тратит ровно 2 часа.
Помогите Рубику найти минимальное количество часов, которое ему понадобится для прохождения всех частей игры. Изначально Рубик может находиться у компьютера, который он считает нужным.
Выходные данные
В единственной строке выведите ответ на задачу.
Примечание
Пояснение ко второму примеру: перед началом игры выгоднее всего находиться у 3-го компьютера. Сначала пройдем часть номер 5. Далее перейдем к 1-му компьютеру и пройдем 3-ю и 4-ю часть. Далее перейдем ко 2-му компьютеру и пройдем 1-ю и 2-ю часть. В сумме получаем 1+1+2+1+2, что равно 7 часам.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5 8 2
1 4
1 3
3 3
1 2
1 1
2 1
1 5
2 2
|
4
2 1 2 1 2 1 2 2
|