Задача Minbus. Службовий автобус робить один рейс за встановленим маршрутом і в разі наявності вільних місць підбирає робітників, які очікують на зупинках, і відвозить їх на завод. Автобус також може чекати на зупинці робітників, які ще не прийшли. Відомо час приходу кожного робітника на свою зупинку і час проїзду автобуса від кожної зупинки до наступної. Автобус приходить на першу зупинку в нульовий момент часу. Тривалість посадки робітників в автобус вважається нульовою. Потрібно написати програму, яка визначить мінімальний час, за який автобус привезе максимально можливу кількість робітників.
Технічні умови. Програма Minbus читає з пристрою стандартного введення в першому рядку кількість зупинок 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
Виведення
4