eolymp
bolt
Try our new interface for solving problems
Problems

Відео-кафе Ужляндії

Відео-кафе Ужляндії

Time limit 1.5 second
Memory limit 128 MiB

Як відомо, чемпіонат світу з хокею в 2014 році пройде в Ужляндії. Для успішного проведення заходу приймаючій стороні належить виконати ряд вимог, що пред'являються Міжнародної хокейної федерацією. Хокейні матчі планується провести в м.Ужкачево та м.Ужковель (в Ужляндіїї усі міста починаються на Уж). Дані міста пов'язані між собою прямою автомагістраллю Ужкачево - Ужковель.

Голова Міжнародної хокейної федерації зазначив, що ні на одному з N кемпінгів, розташованих на автомагістралі Ужкачево - Ужковель немає відео-кафе. Відео-кафе - це елемент придорожнього сервісу, практично нічим не відрізняється від звичайного придорожнього кафе, але в якому створені умови для відео перегляду спортивних подій. Міжнародна хокейна федерація ухвалила, що на К з N існуючих кемпінгів необхідно побудувати відео-кафе. Міжнародна хокейна федерація також встановила такі вимоги до розташування кожного відео-кафе:

1. Якщо по дорозі з м.Ужкачево в м.Ужковель зупинитися в деякому відео-кафе, то відстань між даними відео-кафе і попереднім на автомагістралі відео-кафе (якщо таке є) повинно бути не менше А км і не більше В км.

2. Якщо по дорозі з м.Ужкачево в м.Ужковель зупинитися в деякому відео-кафе, то відстань між даними відео-кафе і наступним на автомагістралі відео-кафе (якщо таке є) повинно бути не менше А км і не більше В км.

3. Відстань від м.Ужкачево та м.Ужковель до найближчого відео-кафе не повинно бути менше А км і не більше В км.

Рисунок до прикладу №1: N=5, K=3, A=20, B=70.

Для кожного i-го побудованого відео-кафе введемо коефіцієнт Z_i - відстань від даного відео-кафе до всіх інших. Міжнародна хокейна федерація встановила, що чим більша сума коефіцієнтів Z_i, тим cвоєчасніше мандрівники зможуть отримувати інформацію про проведення хокейних матчів.

Ваше завдання визначити максимальну суму Z_i, яка може бути досягнута шляхом зведення K відео-кафе, що задовольняють всім вимогам Міжнародної хокейної федерації. Відомо що, кожен кемпінг може містити на своїй території не більше одного відео-кафе. Вірне і зворотнє - відео-кафе може розташовуватися тільки на території кемпінгу.

Формат вхідних даних: Перший рядок вхідного файлу містить два цілих числа - N, K (1 ≤ K ≤ N ≤ 1000) відповідно.

Другий рядок вхідного файлу містить два цілих числа A, B (1 ≤ A < B ≤ 10^9).Третій рядок вхідного файлу містить одне ціле число S (1 ≤ S ≤ 10^9) - відстань між м.Ужкачево та м.Ужковель.Четвертий рядок вхідного файлу містить N цілих чисел C_i (0 < C_i < S, C_i < C_j якщо i < j) - відстань i-го кемпінгу від м.Ужкачево.

Формат вихідних даних: Вихідний файл повинен містити одне ціле число - максимальну суму коефіцієнтів Z_i побудови K відео-кафе. Рішення завжди існує.

Пояснення до прикладів:

У першому прикладі кемпінги {1, 2, 4}

У другому прикладі кемпінги {2, 5, 8, 10}.

Examples

Input example #1
5 3
20 70
195
30 70 90 135 170
Output example #1
420