Задание №26: Обработка данных с помощью сортировки

Кузнечик Кузя прыгает по столбикам, расположенным на координатной прямой, в положительном направлении. На каждом столбике лежит одна золотая монета: попав на столбик, Кузя забирает её с собой. Кузя каждый раз прыгает на следующий столбик, он не может пропускать столбики, перепрыгивая через них. Кузя может допрыгнуть до следующего столбика, если расстояние между столбиками не более K единиц. Кроме того, M раз он может совершить супер-прыжок на расстояние не более, чем L единиц. Если Кузя не может допрыгнуть до следующего столбика, его маршрут завершается. Кузя не может дважды посещать один столбик. Кузя может начать маршрут на любом столбике. Определите наибольшее возможное количество монет, которые может собрать Кузя, а также позицию столбика, на котором заканчивается оптимальный маршрут. Если таких маршрутов несколько, выберите наименьшую возможную позицию последнего столбика.
Входные данные представлены в файле 26-194.txt следующим образом. В первой строке входного файла записаны числа N – количество столбиков (1 ≤ N ≤ 1 000 000), K – длина обычного прыжка (1 ≤ K ≤ 100), L – длина супер-прыжка (K < L ≤ 100) и M – количество возможных супер-прыжков (1 ≤ M ≤ 100). В каждой из следующих N строк записана позиция столбика – натуральное число, не превышающее 1 000 000.
Запишите в ответе два целых числа: сначала количество монет, которые может собрать Кузя, затем – позицию столбика, на котором заканчивается оптимальный маршрут.
Пример входного файла:

6 2 4 1
8
13
1
19
15
9

При таких исходных данных максимальное количество монет, которые может собрать Кузя, – 4 (на столбиках в позициях 8, 9, 13 и 15). Ответ: 4 15.