|
Остановки
(Время: 1 сек. Память: 16 Мб Сложность: 64%)
Представьте себе, что вы - один из проектировщиков железной дороги. Вам нужно построить N остановок, размеры которых довольно велики, но все равны между собой и равны некоторому числу w. Стоимость постройки меняется в зависимости от рода поверхности, по которой предстоит строить платформу. При этом остановки не должны располагаться от границ дороги и друг от друга дальше, чем на R метров, иначе каким-то жителям области придется далеко ходить. Также остановки не должны располагаться от границ дороги и друг к другу ближе, чем на r метров, иначе электрички не будут успевать разгоняться между остановками, и будут медленно ездить. Руководство хочет потратить на постройку остановок минимальное количество денег. Вам известны стоимости постройки метра платформы на каждом из L метров всей дороги. Стоимость i-го метра - ai (при 1 ≤ i ≤ L). Вычислите минимально возможную стоимость расстановки всех остановок.
Входные данные
В первой строке входного файла INPUT.TXT содержатся целые числа N, w и L (1 ≤ N ≤ 100, 1 ≤ w ≤ 100, 1 ≤ L ≤ 20 000). Во второй строке содержится два целых числа: r и R (0 ≤ r ≤ R ≤ 1000). В третьей строке содержится L целых чисел ai, разделенных пробелами (1 ≤ ai ≤ 10000).
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число - искомый ответ. Если решения не существует, то следует вывести «No solution.» .
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 1 5
0 1
3 7 1 5 2
| 6 |
| 2 | 2 3 9
1 2
8 1 2 3 7 4 3 1 11
| 14 |
| 3 | 1 1 1
10 10
239
| No solution. |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
