eolymp
Competitions

XIII Всеукраинская олимпиада по информатике, Киев, Март 27 - Апрель 1, 2000

Автобус

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

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

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

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

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

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

Time limit 1 second
Memory limit 64 MiB
Input example #1
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4
Output example #1
4
Source 2000 XIII All-Ukrainian Informatics Olympiad, Kiev, March 27 - April 1, Round 1