Залізничні квитки#3661

Залізничні квитки

1 секунда

122,812 мегабайта

Дуже легка

На залізничній лінії "Дрезден-Лінц" знаходиться декілька станцій. Лінія подається відрізком, а станції — точками на ньому. Залізниця починається у Дрездені і завершується у Лінці, тому станції нумеруються починаючи з Дрездена (має номер $1$ ), а Лінц — остання станція.

Вартість квитка між двома станціями залежить лише від відстані між ними. Вартість квитків визначається у наступній таблиці.

Прямі квитки (без пересадок) між станціями можна придбати, лише якщо відстань між ними не перевищує $L_{3}$ L_3. Тому іноді доведеться купувати декілька квитків, щоб дістатися від однієї станції до іншої.

Наприклад, на рисунку зверху наведено залізничну лінію з декількома станціями. Придбати прямий квиток від другої до шостої станції неможливо. Існує декілька способів заплатити за проїзд між цими станціями. Наприклад, можна придбати два квитки: один квиток по ціні $C_{2}$ C_2 для проїзду від другої до третьої станції, а другий по ціні $C_{3}$ C_3 для проїзду від третьої до шостої. Зауважимо, що хоча відстань між другою і шостою станціями у точності дорівнює $2 L_{2}$ 2L_2, придбати два квитки по ціні $C_{2}$ C_2 неможливо, так як кожен квиток дійсний лише на одну поїздку, а поїздка обов'язково повинна починатися зі станцій.

Напишіть програму, яка знайде найменшу вартість проїзду між двома станціями.

Вхідні дані

Перший рядок містить $6$ цілих чисел $L_{1}$ L_1, $L_{2}$ L_2, $L_{3}$ L_3, $C_{1}$ C_1, $C_{2}$ C_2, $C_{3}$ C_3 ( $1 \leq L_{1} < L_{2} < L_{3} \leq 1 0^{9}$ 1 \leq L_1 < L_2 < L_3 \leq 10^9, $1 \leq C_{1} < C_{2} < C_{3} \leq 1 0^{9}$ 1 \leq C_1 < C_2 < C_3 \leq 10^9) у вказаному порядку, відокремлені одним пропуском.

Другий рядок містить кількість станцій $N$ ( $2 \leq N \leq 10000$ 2 \leq N \leq 10000).

Третій рядок містить два різних цілих числа — номери станцій, вартість проїзду між якими потрібно знайти.

Наступні $N - 1$ N - 1 рядків містять відстані між першою станцією (Дрезден) та кожною з інших. Відстані задано як натуральні числа і розміщені у зростаючому порядку. Відстань між Дрезденом та Лінцом не перевищує $1 0^{9}$ 10^9. Відстань між довільними сусідніми станціями не перевищує $L_{3}$ L_3. Найменша вартість проїзду між двома заданими станціями не перевищує $1 0^{9}$ 10^9.

Вихідні дані

Виведіть одне число — найменшу вартість поїздки між двома заданими станціями.

Приклади

Приклад 1