|
КЕГЭ-27. Основная волна 2022-II (Источник kompege.ru задание 4630)
.На кольцевой автодороге с двусторонним движением находится N многоэтажных жилых домов
(не более одного дома на каждом километре дороги).
Длина кольцевой автодороги равна K км. Нулевой километр и K-й километр находятся в одной точке.
Жители домов ежедневно получают почту. Которую доставляют роботы-почтальоны.
Почта упакована в доставочные пакеты, каждый из которых вмещает не более 9 кг посылок или писем.
Каждый доставочный пакет используется для доставки почты только в один жилой дом,
при этом в каждый дом может быть доставлено не более одного пакета с неполной загрузкой.
Известно, что заряд аккумулятора робота-почтальона позволяет проходить ему не более M км,
заряд аккумулятора для возвращения робота в почтовое отделение не учитывается.
Почтовое отделение открыли в одном из домов таким образом,
чтобы количество доставляемых пакетов с корреспонденцией было максимальным.
В каждом доставочном пакете перевозится почта только для одного дома.
Определите необходимое количество доставочных пакетов в этом почтовом отделении.
Входные данные
Дано два входных файла (файл A и файл B), каждый из которых
в первой строке содержит три числа N, K и M (1 ≤ N, K, M ≤ 107)
число N – количество жилых домов, число K -длина кольцевой дороги в километрах
и число M - максимальное расстояние, на которое робот может осуществлять доставку почтовых отправлений.
В каждой из следующих N строк находится два числа:
номер километра кольцевой автодороги, на котором расположен жилой дом, и вес ежедневной корреспонденции
(все числа натуральные, вес писем и посылок для каждого дома не превышает 1000 кг).
Числа указаны в порядке расположения домов на автодороге.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла В.
Типовой пример организации данных во входном файле
5 11 3
1 8
3 7
5 6
7 5
9 3
При таких исходных данных и вместимости пакета 3 кг максимальное количество пакетов
для доставки корреспонденции из оптимального расположения почтового отделения составит: 3+3+2
Выходные данные
В ответе укажите два числа: сначала длину искомой подпоследовательности для файла А, затем для файла B.
|