Хемуль построил телескоп для наблюдения за кометой. Поскольку это очень сложный прибор, его требуется настроить. Настройка телескопа заключается в последовательном выполнении шести операций строго в указанном порядке: O1, O2, O3, O4, O5, O6. В Муми-доле живут четыре мастера, каждый из которых умеет осуществлять некоторые из этих операций. Ниже приведена таблица, указывающая, какие операции может осуществлять какой мастер:
|
Мастер |
Операции, которые он умеет выполнять |
|
Мастер1 |
O1, O5, O6 |
|
Мастер2 |
O2, O3, O5 |
|
Мастер3 |
O1, O2, O4 |
|
Мастер4 |
O3, O4, O6 |
Жилища мастеров расположены на некотором расстоянии друг от друга. Время, которое необходимо Хемулю, чтобы перенести телескоп от жилища одного мастера до жилища другого мастера, приведено в таблице:
|
|
Мастер1 |
Мастер2 |
Мастер3 |
Мастер4 |
|
Мастер1 |
----------- |
1 час |
2 часа |
3 часа |
|
Мастер2 |
1 час |
----------- |
3 часа |
2 часа |
|
Мастер3 |
2 часа |
3 часа |
----------- |
1 час |
|
Мастер4 |
3 часа |
2 часа |
1 час |
----------- |
Хемуль очень педантичен, поэтому он начинает свой путь с посещения одного из мастеров, которые могут выполнить операцию O1, затем переносит телескоп к мастеру, который может выполнить операцию O2 и т.д., всегда используя прямую дорогу между соответствующими мастерами и затрачивая на нее время, указанное в таблице.
Каждый мастер затрачивает на каждую операцию одинаковое количество времени – 1 час. Мастер начинает работать тот час же, как только Хемуль приходит в его жилище. Хемуль покидает жилище мастера и отправляется к следующему тот час же, как только мастер заканчивает операцию. Если мастер может выполнить две идущие подряд операции – Хемуль может остаться в его жилище и дать ему возможность выполнить обе операции.
Найдите для Хемуля оптимальную последовательность посещения мастеров, чтобы он затратил минимальное время на полную настройку телескопа. Посчитайте для этой последовательности (она может быть не единственна) время в часах от момента, когда Хемуль пришел в жилище мастера, который может выполнить операцию O1 до окончания одним из мастеров выполнения операции O6. В ответе укажите целое число