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