Магистр Аркадий любит путешествовать на поезде. Он собирается отправиться в множество поездок в течение года и заранее знает, в какие дни он поедет.
Аркадий может купить билеты по разным тарифам:
- 1-дневный тариф стоит
C1 рублей;
- 7-дневный тариф стоит
C2 рублей;
- 30-дневный тариф стоит
C3 рублей.
Каждый билет начинает действовать с того дня, когда был куплен.
Например, если Аркадий купит 7-дневный билет на 2-й день путешествия, то он сможет путешествовать 7 дней: 2, 3, 4, 5, 6, 7 и 8 дни.
Помогите Аркадию найти минимальную стоимость, за которую можно купить билет(ы), чтобы он мог отправиться путешествовать в любой из запланированных дней.
Входные данные
Первая строка содержит натуральное число
n - количество дней, в которые Аркадий планирует путешествовать. Вторая строка содержит порядковые номера дней, в которые Аркадий планирует путешествовать (
daysi). Третья строка содержит три числа:
C1, C2, C3.
Ограничения:
1 <= n <= 3651 <= daysi <= 365- Порядковы номера дней
daysi даются в строго возрастающем порядке.
1 <= С1, С2, С3 <= 1000
Выходные данные
Выведите минимальное количество рублей, которое Аркадию придется заплатить за билеты.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6
1 4 6 7 8 20
2 7 15
|
11
|
| 2 |
12
1 2 3 4 5 6 7 8 9 10 30 31
2 7 15
|
17
|