eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Автобус

Автобус

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Служебный автобус совершает один рейс по установленному маршруту и в случае наличия свободных мест подбирает рабочих, которые ожидают на остановках, и отвозит их на завод. Автобус также может ждать на остановке рабочих, которые еще не пришли. Известно время прихода каждого рабочего на свою остановку и время проезда автобуса от каждой остановки до следующей. Автобус приходит на первую остановку в нулевой момент времени. Продолжительность посадки рабочих в автобус считается нулевой.

Написать программу, которая определит минимальное время, за которое автобус привезет максимально возможное количество рабочих.

Входные данные

Первая строка содержит количество остановок N и количество мест в автобусе M. Каждая i-я строчка из последующих N строчек содержит целое число - время движения от остановки і к остановке i + 1 (N + 1 -я остановка - завод), количество рабочих K, которые придут на i-ю остановку, и время прихода каждого рабочего на эту остановку в порядке прихода. Известно, что 1 M 2000, 1 N, K 200000.

Выходные данные

Вывести минимальное время, необходимое для перевозки максимального количества рабочих.

Пример

Входные данные #1
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4
Выходные данные #1
4
Источник 2000 XIII Всеукраинская олимпиада по информатике, Киев, Март 27 - Апрель 1, тур 1