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