Экспедиция к звезде
(Время: 0,25 сек. Память: 32 Мб Сложность: 66%)
Исследовательский космический корабль отправляется в экспедицию к Солнцу. Расстояние от стартовой орбиты до цели составляет R километров. В начале полёта корабль полностью заправлен и может пролететь V километров без дозаправки. Топливо расходуется равномерно: 1 единица топлива – 1 километр пути. По пути корабль встречает N метеоритных скоплений.
Каждое скопление расположено на определённом расстоянии от стартовой точки xi и содержит некоторое количество вещества wi, которое можно переработать в топливо.
При подлёте к метеоритному скоплению корабль может остановиться, переработать вещество скопления, пополнить запас топлива на указанное количество единиц, но при этом общий запас топлива не может превышать вместимость топливных баков V.
Корабль может остановиться только в точках расположения метеоритных скоплений. Повторное посещение одного и того же скопления невозможно.
Определите, какое минимальное количество метеоритных скоплений придется посетить, чтобы достигнуть Солнца, а также минимально возможную координату метеоритного скопления, которое получится посетить последний раз.
Входные данные
В первой строке входного файл INPUT.TXT заданы три натуральных числа N, R, V. В следующих N строках записано по два натуральных числа xi и wi через пробел. (1 ≤ N ≤ 2×105; 1 ≤ V < R ≤ 15×108; 1 ≤ xi, wi ≤ 15×108).
Выходные данные
В выходной файл OUTPUT.TXT выведите два натуральных числа: минимальное количество метеоритных скоплений и минимальная координата метеоритного скопления, на котором будет выполнена последняя остановка.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 7 50 20
10 20
19 9
15 11
40 20
31 5
41 10
30 10 | 3 40 |
Пояснение к примеру
Здесь можно сделать 3 остановки: {15, 30, 41} или {15, 30, 40} или {10, 30, 40}. Поэтому ответ: 3 40.
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
