№198036331
(Л. Шастин) Дальнобойщику необходимо добраться до пункта выгрузки товаров, для чего ему предстоит преодолеть путь длиной R километров. В начале пути топливный бак грузовика полон и вмещает в себя такое количество бензина, которого достаточно, чтобы проехать V километров. Имеется информация о количестве заправочных станций на пути и километрах, на которых они расположены.
Определите, какое минимальное количество раз придется заправиться дальнобойщику, чтобы достигнуть пункта выгрузки товаров, а также минимально возможный километр, на котором получится заправиться в последний раз.
Входные данные
В первой строке входного файла находится три натуральных числа: N (N ≤ 10 000) - количество заправочных станций, R (R ≤ 10 000 000) - длина пути и V (V < R) - количество километров, которые можно проехать с полностью заправленным баком. В следующих N строках находятся километры, обозначающие расположение заправочных станций. Каждое из чисел целое, не превосходящее 10 000 000.
Запишите в ответе два числа: минимальное количество заправок, которые придется выполнить, чтобы достигнуть пункта выгрузки товаров, и, при этих условиях, минимальный возможный номер километра, на котором будет выполнена последняя заправка.
Типовой пример организации данных во входном файле
7 50 23
45
15
23
48
29
7
46
При таких исходных данных можно заправиться 2 раза: {7, 29} или {15, 29} или {23, 29} или {23, 46}. Ответ: 2 29.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.