Задача #815

(В. Рыбальченко) В водоеме растет N кувшинок. На этих кувшинках обожают сидеть лягушки. Люди заметили, что несколько лягушек начинают одновременно перепрыгивать с одной кувшинки на другую. Каждая кувшинка имеет свой номер, отражающий ее положение в водоеме, также известно сколько кувшинка может выдержать лягушек одновременно. Необходимо определить, за какое минимальное количество прыжков К лягушек смогут добраться как можно дальше, при условии, что они начинают с первой подходящей кувшинки и могут максимально перепрыгивать через M штук за раз. Необходимо в ответ указать минимальное количество прыжков, за которое лягушки смогли продвинуться максимально далеко и номер последней кувшинки, до которой смогут добраться лягушки.

Входные данные представлены в файле следующим образом. В первой строке входного файла записано число N (1 ≤ N ≤ 20000) – количество кувшинок, число К (1 ≤ К ≤ 5) – количество лягушек, одновременно находящихся на одной кувшинке и число М (1 ≤ М ≤ N) – максимальная длина прыжка через кувшинки. Каждая из следующих N строк содержит два натуральных числа номер кувшинки и максимальное количество лягушек, которые могут находиться одновременно на этой кувшинке.

Пример входного файла:

8 2 3
2 1
4 2
6 4
7 2
8 1
10 3
11 2
13 1

При таких исходных данных лягушки преодолеют следующий маршрут: (4, 2), (7, 2), (10, 3), (11, 2). Ответ 3 11.