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