Степан робить пробіжки за своїм особливим алгоритмом:

• Після старту він біжить із швидкістю ~S~ м/с на протязі ~A~ секунд.
• Потім він зупиняється на ~B~ секунд і відпочиває. Після відпочинку знову продовжує біг.

Скільки метрів пробіжить Степан сьогодні, якщо він виділив на тренування X секунд.

Обмеження

• ~1 \le S \le 15~
• ~1 \le A \le 1000~
• ~1 \le B \le 1000~
• ~1 \le X \le 1000~
• Усі вхідні значення є цілими числами.

Input

Вхідний потік містить чотири цілі числа ~S, A, B, X~

Output

У вихідний потік вивести відповідь.

Sample Input 1

7 3 2 11

Sample Output 1

49

Sample Input 2

6 3 2 9

Sample Output 2

36

Notes

Степан на пробіжку виділив 11 секунд.

• за перші 3 с він пробіжить 21 м.
• з 3 по 5 с він відпочиває.
• з 5 по 8 с він пробігає ще 21 м.
• з 8 по 10 с він відпочиває.
• з 10 по 11 с він пробіжить 7 м.

Отже, всього Степан пробіжить 49 м.

Сьогодні Степан придумав для вас задачку на подільність. Отже, є лінійний масив ~A~, що містить ~N~ цілих чисел та ціле число ~M~.

Степана цікавить, чи можна видалити з масиву одне число таке, щоб сума решти ~N-1~ чисел масиву була кратна ~M~?

Обмеження

• ~2 \le N \le 2 \times 10^5~
• ~2 \le M \le 10^3~
• ~0 \le A_i \le 10^3~

Input

Перший рядок вхідного потоку містить цілі числа ~N, M~.

Наступний рядок містить ~N~ цілих чисел ~A_i~

Output

У вихідний потік вивести ~Yes~ або ~No~ - відповідь на поставлене завдання.

Sample Input 1

3 3
1 2 2

Sample Output 1

Yes

Sample Input 2

3 3
1 1 1

Sample Output 2

No

Група із ~N~ туристів підійшла до переправи на річці. На переправі є човен, який може помістити не більше двох людей. Наближається гроза, і туристам треба якнайшвидше переправитися на той берег річки, де є укриття від дощу.

Відомий час переправи для кожного туриста ~T_i~. Якщо в човні дві людини, то час їх переправи буде дорівнювати більшому часу з двох людей, які знаходяться у човні.

Знайдіть мінімальний час переправи для всієї групи туристів.

Обмеження

• ~3 \le N \le 10^4~
• ~1 \le T_i \le 10^4~

Input

Перший рядок вхідного потоку містить ціле число ~N~ - кількість туристів.

Наступний рядок містить ~N~ цілих чисел ~T_i~ - час переправи для кожного з туристів.

Output

Вивести у вихідний потік одне число - найменший час переправи групи туристів.

Sample Input 1

3
1 10 20

Sample Output 1

31

Sample Input 2

4
1 6 7 8

Sample Output 2

23

Notes

У першому прикладі можливий такий порядок переправи:

• переправляються перший та другий туристи - час рівний 10;
• перший повертається назад - час рівний 1;
• перший та третій переправляються - час рівний 20.

Отже, загальний час, витрачений на переправу, рівний 10 + 1 + 20 = 31.

Людство вже давно ламає голову над однією важливою проблемою: на якому з світлофорів оптимально переходити дорогу.

Оскільки повна версія цієї задачі занадто важка, вам дано простішу версію з наступними правилами:

1. На початку всі світлофори горять червоним.

2. Всі світлофори мають однаковий колір, тобто, якщо один з них горить зеленим – то всі горять зеленим, якщо один червоний – то всі червоні.

3. Вам відомо найближчий час, коли світлофор увімкне зелений: ~T~ і також скільки він може горіти зеленим і червоним: ~G~ і ~R~ відповідно.

4. Дорогу можна починати переходити в мить, коли ввімкнувся зелений, достатньо, щоб зелений горів в мить, коли почався перехід, НЕ обов'язково, щоб зелений горів під час всієї довжини переходу.

5. Відстань між початком шляху і світлофором ~i~: ~d_i~, та довжина вулиці ~D~ така, що ~d_i \le D~, та ширина переходу ~L~.

   Можна уявити, що світлофори розташовані на прямій у порядку ~1, 2, ..., n~, і вулиця це два паралельних відрізки довжиною ~D~ на відстані ~L~.

6. Починаючи в координаті ~0~, потрібно пройти всю довжину вулиці ~D~ і при цьому перейти дорогу на якомусь з світлофорів

Фактично вам відома повна конфігурація світлофорів на вулиці.

Потрібно мінімізувати час проходу вулиці.

Обмеження

~(1 \le D,L \le 10^8)~

~(1 \le T \le R \le 10^8)~

~(1 \le G \le 10^8)~

~(1 \le n \le 10^3)~

~(0 \le d_1 < d_2 <... < d_n \le D)~

Input

~D~ ~L~ ~T~ ~G~ ~R~

~n~

~d_1~ ~d_2~ ~...~ ~d_n~

Output

Мінімальний час проходу вулиці.

Sample Input 1

5 3 1 1 100
3
1 3 5

Sample Output 1

8

Sample Input 2

5 3 1 1 100
3
2 3 5

Sample Output 2

105

Notes

Тест 1: Потрібно пройти до першого світлофора, перейти на ньому дорогу і дійти до кінця вулиці.

Тест 2: Доходячи до першого світлофора, зелений встиг увімкнутись і вимкнутись, тому потрібно дійти до останнього світлофора і чекати зеленого на позиції ~5~.

Фабрика переробляє руду протягом ~n~ стадій. Ціль отримати як можна більше матеріалу типу ~n~.

На кожній стадії доступно кілька машин. Машина переробляє матеріал типу ~T_i~ в матеріал типу ~T_{i+1}~. Кожна окрема машина характеризується тим, скільки матеріалу вона споживає і скільки виробляє: ~I_i~ та ~O_i~.

Оскільки фабрика має обмежений розмір складу ~k~, це значить, що матеріали зберігатимуться разом, тобто склад має вміщати весь матеріал типів ~i~ та ~i+1~, який було вироблено і який залишився.

Зайві матеріали можна викинути з складу. Якщо якась кількість матеріалу була викинута з складу, у фабрики більше не буде до неї доступу.

Етапи переробки мають виконуватись поступово, тобто спершу потрібно переробити тип ~1~ на тип ~2~, потім тип ~2~ на тип ~3~, і так далі, поки не виготовимо бажану кількість типу ~n~.

На початку процесу в наявності лише ~s~ одиниць матеріалу типу ~1~.

Для кожного етапу існує хоча б одна машина.

Визначіть максимальну можливу кількість матеріалу типу ~n~, яку можна отримати.

Обмеження

• ~(2 \le n \le 30)~
• ~(n-1 \le m \le 500)~
• ~(1 \le s \le k \le 10^4)~
• ~(1 \le T_i \le n-1)~
• ~(1 \le I_i, O_i \le k)~

Input

~n~ ~m~

~s~ ~k~

~T_1~ ~I_1~ ~O_1~

~T_2~ ~I_2~ ~O_2~

~\vdots~ ~\vdots~ ~\vdots~

~T_m~ ~I_m~ ~O_m~

Output

Максимальна кількість матеріалу типу ~n~, яку можна отримати.

Sample Input 1

3 5
5 5
1 5 4
1 2 3
1 1 2
2 1 1
2 3 4

Sample Output 1

5

Sample Input 2

4 4
11 24
1 2 3
1 1 1
2 1 5
3 3 4

Sample Output 2

24

Sample Input 3

2 1
4 7
1 2 4

Sample Output 3

7

Sample Input 4

2 1
7 7
1 3 5

Sample Output 4

5