Відео-кафе Ужляндії
Як відомо, чемпіонат світу з хокею в 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}.