Як відомо, чемпіонат світу з хокею в 2014 році пройде в Ужляндії. Для успішного проведення заходу приймаючій стороні належить виконати ряд вимог, що пред'являються Міжнародної хокейної федерацією. Хокейні матчі планується провести в м.Ужкачево та м.Ужковель (в Ужляндії усі міста починаються на Уж). Дані міста пов'язані між собою прямою автомагістраллю Ужкачево - Ужковель.
Голова Міжнародної хокейної федерації зазначив, що ні на одному з кемпінгів, розташованих на автомагістралі Ужкачево - Ужковель немає відео-кафе. Відео-кафе - це елемент придорожнього сервісу, практично нічим не відрізняється від звичайного придорожнього кафе, але в якому створені умови для відео перегляду спортивних подій. Міжнародна хокейна федерація ухвалила, що на з існуючих кемпінгів необхідно побудувати відео-кафе. Міжнародна хокейна федерація також встановила такі вимоги до розташування кожного відео-кафе:
Якщо по дорозі з м.Ужкачево в м.Ужковель зупинитися в деякому відео-кафе, то відстань між даними відео-кафе і попереднім на автомагістралі відео-кафе (якщо таке є) повинно бути не менше км і не більше км.
Якщо по дорозі з м.Ужкачево в м.Ужковель зупинитися в деякому відео-кафе, то відстань між даними відео-кафе і наступним на автомагістралі відео-кафе (якщо таке є) повинно бути не менше км і не більше км.
Відстань від м.Ужкачево та м.Ужковель до найближчого відео-кафе не повинно бути менше км і не більше км.
Рисунок до прикладу №1: N=5, K=3, A=20, B=70.
Для кожного -го побудованого відео-кафе введемо коефіцієнт Z_i - відстань від даного відео-кафе до всіх інших. Міжнародна хокейна федерація встановила, що чим більша сума коефіцієнтів Z_i, тим своєчасніше мандрівники зможуть отримувати інформацію про проведення хокейних матчів.
Ваше завдання визначити максимальну суму Z_i, яка може бути досягнута шляхом зведення відео-кафе, що задовольняють всім вимогам Міжнародної хокейної федерації. Відомо що, кожен кемпінг може містити на своїй території не більше одного відео-кафе. Вірне і зворотне - відео-кафе може розташовуватися тільки на території кемпінгу.
Перший рядок вхідного файлу містить два цілих числа — , (1 \leq K \leq N \leq 1000) відповідно.
Другий рядок вхідного файлу містить два цілих числа , (1 \leq A < B \leq 10^9).
Третій рядок вхідного файлу містить одне ціле число (1 \leq S \leq 10^9) — відстань між м.Ужкачево та м.Ужковель.
Четвертий рядок вхідного файлу містить цілих чисел C_i (0 < C_i < S, C_i < C_j якщо i < j) — відстань -го кемпінгу від м.Ужкачево.
Вихідний файл повинен містити одне ціле число — максимальну суму коефіцієнтів Z_i побудови відео-кафе. Рішення завжди існує.
Example 1
Example 2
У першому прикладі кемпінги \{1, 2, 4\}.
У другому прикладі кемпінги \{2, 5, 8, 10\}.
K \leq 2 — не менше 15 балів
N^K \leq 10^6 — не менше 30 балів
N \leq 50 — не менше 45 балів
N \leq 300 — не менше 60 балів