Задание №42273 ЕГЭ по Информатике

Исследователь отправляется в экспедицию через пустыню, чтобы добраться до древнего храма, расположенного на расстоянии R километров от стартовой точки (которая определена первым километром). В начале пути его верблюд полностью отдохнул и может пройти V километров без остановки. По пути расположены оазисы, в которых можно напоить верблюда и позволить ему восстановить силы, чтобы снова пройти до V километров. Известны координаты N оазисов — километры от начала пути, на которых они расположены, а также запас воды в каждом из них (в у.е.). Каждая 1 у.е. воды эквивалентна 1 километру пути, который может преодолеть верблюд. Определите, какое минимальное количество оазисов придётся посетить, чтобы достичь древнего храма, а также минимально возможный номер километра расположения оазиса, который получится посетить последний раз. Входные данные В первой строке входного файла находится три натуральных числа: N (N ≤ 100 000) — количество оазисов на пути, R (R ≤ 10 000 000) — расстояние от стартовой точки до храма, и V (V < R) — максимальное количество километров, которые может пройти полностью отдохнувший верблюд. В следующих N строках находятся по два числа: расстояние (в километрах) между стартовой точкой и очередным оазисом, и запас воды в каждом из них (в у.е.). Каждое из чисел целое, не превосходящее 10 000 000. Выходные данные Запишите в ответе два числа: минимальное количество оазисов, которые придётся посетить, чтобы достичь древнего храма, и при этих условиях минимальный возможный номер километра (с оазисом), на котором будет выполнена последняя остановка. Типовой пример организации данных во входном файле
7 50 20
10 20
19 9
15 11
40 20
31 5
41 10
30 10
При таких исходных данных можно сделать 3 остановки: {15, 30, 41} или {15, 30, 40} или {10, 30, 40}. Ответ: 3 40. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.