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