Задачи
Железнодорожные билеты
Железнодорожные билеты
На железнодорожной линии "Екатеринбург-Свердловск" находится несколько станций. Линия представляется отрезком, а станции - точками на нем. Железная дорога начинается в Екатеринбурге и заканчивается в Свердловске, поэтому станции нумеруются начиная с Екатеринбурга (имеет номер \textbf{1}), а Свердловск - последняя станция.
\includegraphics{https://static.e-olymp.com/content/a3/a3acb98b91616b597797f79718c73f732a394eb3.jpg}
Стоимость билета между двумя станциями зависит только от расстояния между ними. Стоимость билетов определяется в следующей таблице.
Прямые билеты (без пересадок) между станциями можно приобрести, только если расстояние между ними не превосходит \textbf{L_3}. Поэтому иногда придется приобретать несколько билетов, чтобы добраться от одной станции до другой.
Например, на рисунке вверху приведена железнодорожная линия с несколькими станциями. Приобрести прямой билет со второй до шестой станции невозможно. Существует несколько способов заплатить за проезд между этими станциями. Например, можно приобрести два билета: один билет по цене \textbf{C_2} для проезда со второй до третьей станции, а второй по цене \textbf{C_3} для проезда от третьей до шестой. Отметим, что хотя расстояние между второй и шестой станциями в точности равно \textbf{2L_2}, приобрести два билета по цене \textbf{C_2} невозможно, так как каждый билет действителен только на одну поездку, а поездка обязательно должна начинаться со станций.
Напишите программу, которая найдет наименьшую стоимость проезда между двумя станциями.
\InputFile
Первая строка содержит \textbf{6} целых чисел \textbf{L_1}, \textbf{L_2}, \textbf{L_3}, \textbf{C_1}, \textbf{C_2}, \textbf{C_3} (\textbf{1 }≤ \textbf{L_1} < \textbf{L_2} < \textbf{L_3} ≤ \textbf{10^9}, \textbf{1 }≤ \textbf{C_1} < \textbf{C_2} < \textbf{C_3} ≤ \textbf{10^9}) в указанном порядке, разделенные одним пробелом. Вторая строка содержит количество станций \textbf{N }(\textbf{2 }≤ \textbf{N }≤ \textbf{10000}). Третья строка содержит два разных целых числа - номера станций, стоимость проезда между которыми следует найти. Следующие \textbf{N - 1 }строк содержат расстояния между первой станцией (Екатеринбург) до каждой из остальных. Расстояния заданы как натуральные числа и расположены в возрастающем порядке. Расстояние между Екатеринбургом и Свердловском не превышает \textbf{10^9}. Расстояние между любыми соседними станциями не превышает \textbf{L_3}. Наименьшая стоимость проезда между двумя заданными станциями не превышает \textbf{10^9}.
\OutputFile
Выведите одно число - наименьшую стоимость поездки между двумя заданными станциями.
Входные данные #1
3 6 8 20 30 40 7 2 6 3 7 8 13 15 23
Выходные данные #1
70