Видеокафе Ужляндии
Как известно, чемпионат мира по хоккею 2014 года пройдет в Ужляндии. Для успешного проведения мероприятия принимающая сторона должна выполнить ряд требований, предъявляемых Международной хоккейной федерацией. Хоккейные матчи планируется провести в городах Ужкачево и Ужковель (в Ужляндии все города начинаются на "Уж"). Эти города соединены прямой автомагистралью Ужкачево - Ужковель.
Глава Международной хоккейной федерации отметил, что ни на одном из N кемпингов, расположенных на автомагистрали Ужкачево - Ужковель, нет видео-кафе. Видео-кафе — это элемент придорожного сервиса, практически ничем не отличающийся от обычного придорожного кафе, но в котором созданы условия для просмотра спортивных событий. Международная хоккейная федерация постановила, что на К из N существующих кемпингов необходимо построить видео-кафе. Международная хоккейная федерация также установила следующие требования к расположению каждого видео-кафе:
1. Если по дороге из Ужкачево в Ужковель остановиться в некотором видео-кафе, то расстояние между данным видео-кафе и предыдущим на автомагистрали видео-кафе (если такое есть) должно быть не менее А км и не более В км.
2. Если по дороге из Ужкачево в Ужковель остановиться в некотором видео-кафе, то расстояние между данным видео-кафе и следующим на автомагистрали видео-кафе (если такое есть) должно быть не менее А км и не более В км.
3. Расстояние от Ужкачево и Ужковель до ближайшего видео-кафе не должно быть менее А км и не более В км.
Рисунок к примеру №1: N=5, K=3, A=20, B=70.
Для каждого i-го построенного видео-кафе введем коэффициент Z_i — расстояние от данного видео-кафе до всех остальных. Международная хоккейная федерация установила, что чем больше сумма коэффициентов Z_i, тем своевременнее путешественники смогут получать информацию о проведении хоккейных матчей.
Ваша задача — определить максимальную сумму 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}.