Олимпиада информатика сириус вош

Путь Пети в школу пролегает через оживлённый перекресток. На этом перекрёстке есть светофоры для пешеходов и светофоры для автомобилей.
Пешеходы могут переходить дорогу только по пешеходным переходам.
Пронумеруем пешеходные переходы числами от 1
до 4
так, как показано на рисунке.
Углы перекрёстка будем обозначать комбинациями цифр 12
, 23
, 34
и 41
—
по номерам переходов, которыми можно воспользоваться, находясь на этом углу.
Для каждого перехода известно время RJ
, в течение которого пешеходам горит красный свет, и время GJ
, в течение которого пешеходам горит зелёный свет (J=1
, 2
, 3
, 4
). Также для каждого перехода известно время TJ
, за которое его может перейти Петя.


Петя будет переходить ту или иную дорогу только в том случае, если успеет полностью перейти её на зелёный свет.
Чтобы попасть в школу, Пете нужно перейти с угла 12
на угол Y
(Y≢12
). Известно, что в тот момент, когда Петя достиг угла 12
, на всех пешеходных светофорах включился красный свет.
Ваша задача —
определить, через какое минимальное время Петя сможет попасть на угол Y
.

Формат входных данных
В первой строке содержится число Y
(Y
∈
{23
, 34
, 41
}) —
обозначение угла, на который нужно попасть Пете.
Во второй строке содержатся три целых числа R1
, G1
, T1
, записанных через пробел.
В третьей строке содержатся три целых числа R2
, G2
, T2
, записанных через пробел.
В четвёртой строке содержатся три целых числа R3
, G3
, T3
, записанных через пробел.
В пятой строке содержатся три целых числа R4
, G4
, T4
, записанных через пробел.
Здесь RJ
—
время, в течение которого на переходе J
горит красный свет, GJ
—
время, в течение которого на переходе J
горит зелёный свет, TJ
—
время, в течение которого Петя может пересечь переход J
(J=1
, 2
, 3
, 4
). Все числа положительные и не превосходят 106
.

Формат выходных данных
Выведите целое число —
минимальное время, которое потребуется Пете, чтобы попасть с угла 12
на угол Y
.
Гарантируется, что Петя всегда может перейти на угол Y
.

Система оценки
В этой задаче применяется потестовая оценка.
Верные решения, предполагающие, что TJ≤GJ
, могут набрать от 80
баллов.

Замечание
Поясним приведённые примеры.
Рассмотрим первый пример.
Предположим, что Петя решил идти на угол 34
через угол 23
. В этом случае он сначала дождётся окончания красного сигнала на переходе 2
—
это произойдёт через 120
секунд, после чего перейдёт на угол 23
за 14
секунд. Таким образом, он окажется на этом углу в момент 134
.
Теперь ему нужно пройти по переходу 3
. К моменту 134
на светофоре перехода 3
горит красный сигнал. Действительно, в течение 60
секунд горел красный, затем в течение 22
секунд горел зелёный, и в момент 82
секунды вновь включился красный, который будет гореть до момента 142
секунды. Таким образом, Пете придётся подождать 8
секунд, после чего он сможет перейти дорогу за 10
секунд и окажется на углу 34
в момент 152
секунды.
Рассмотрим другую возможность: пусть Петя решил идти на угол 34
через угол 41
. В этом случае он будет ожидать на переходе 1
в течение 80
секунд, пока горит красный, а затем перейдёт дорогу за 12
секунд и окажется на углу 41
в момент 92
секунды.
Далее Пете нужно перейти по переходу 4
. В момент 90
на переходе 4
красный сигнал светофора сменился на зелёный, при этом горит зелёный сигнал в течение 18
секунд. Это значит, что в момент, когда Петя окажется на углу 41
, зелёный сигнал уже будет гореть в течение 2
секунд, так что на переход Петя может потратить до 16
секунд. Нам известно, что на пересечение этого перехода Пете требуется 14
секунд, поэтому Петя может сразу начать движение по переходу 4
. На углу 34 ......