Задача 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

© LIKT 1998-2018