Задание выполняется с использованием прилагаемых файлов.
У концерна по производству пастеризованного молока есть N ферм. Все фермы расположены вдоль некоторого прямолинейного пути и имеют номера, соответствующие расстоянию от нулевой отметки до конкретной фермы. Известно количество литров молока, которое ежедневно получают на каждой ферме.
Концерн планирует открыть молокоперерабатывающий завод при одной из ферм. Перевозить молоко разрешается на расстояние не более М. Молоко перевозят в бидонах вместимостью 15 литров каждый. Каждая ферма имеет свой набор бидонов для перевозки молока, при этом с каждой фермы на завод может быть доставлено не более одного неполного бидона. Место для возведения завода выбрано так, чтобы количество доставляемых туда бидонов с молоком было максимальным.
Определите необходимое общее количество бидонов для доставки молока на этот завод.
Входные данные
Даны два входных файла (файл А и файл В), каждый из которых в первой строке содержит два числа N и М (1 ≤ N ≤ 10 000 000, 1 ≤ М ≤ 10 000 000) - количество ферм и максимальное расстояние, на которое разрешено перевозить молоко с соответствующей фермы. В каждой из следующих N строк находятся два числа: номер фермы и количество литров молока (в литрах), производимых на этой ферме за сутки (все числа натуральные, количество литров молока на каждой ферме не превышает 1000). Фермы перечислены в порядке их расположения вдоль пути, считая от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем - для файла В.
Типовой пример организации данных во входном файле
6 5
1 112
5 204
10 50
11 20
12 20
13 33
При таких исходных данных и вместимости бидона, составляющей 10 литров, концерну выгодно открыть молокоперерабатывающий завод в пункте 5. В этом случае количество бидонов, привозимых на завод за сутки: 12 + 21 + 5.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла В не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.