• Автобус
  BUS

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

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

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

Пример входных данных
3  5
1  2  0  1
1  1  2
1  4  0  2  3  4

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

Пример выходных данных.
4