eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Железнодорожные билеты

Железнодорожные билеты

На залізничній лінії "Єкатеринбург-Свердловськ" знаходиться декілька станцій. Лінія подається відрізком, а станції - точками на ньому. Залізниця починається у Єкатеринбурзі і завершується у Свердловську, тому станції нумеруються починаючи з Єкатеринбурга (має номер \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 секунда
Ліміт використання пам'яті 122.81 MiB
Вхідні дані #1
3 6 8 20 30 40
7
2 6
3
7
8
13
15
23
Вихідні дані #1
70
Автор Павло Залецький
Джерело 1999 III Командний Студентський Чемпіонат Уралу, Єкатеринбург, Березень 19 - 20, Задача D