Службовий автобус здійснює один рейс по встановленому маршруту і у випадку наявності вільних місць підбирає робітників, які чекають на зупинках, і відвозить їх на завод. Автобус також може чекати на зупинці робітників, які ще не прийшли. Відомий час приходу кожного робітника на свою зупинку і час проїзду автобуса від кожної зупинки до наступної. Автобус приходить на першу зупинку у нульовий момент часу. Тривалість посадки робітників в автобус вважаються нульовою.

Написати програму, яка визначить мінімальний час, за який автобус привезе максимально можливу кількість робітників.

Вхідні дані

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

Вихідні дані

Вивести мінімальний час, необхідний для перевезення максимальної кількості робітників.