24342번 - УЧИЛИЩЕН АВТОБУС 다국어

Училищен автобус може да вози най-много М ученици. Авобусът всеки ден вози ученици до училището по установен маршрут, който включва няколко спирки. На всяка спирка в атобуса се качват ученици, ако има свободни места. Също автобусът може да чака на спирката ученици, които все още не са дошли. Известни са времената за придвижване на автобуса от една спирка до следващата, както и моментите на пристигане на всеки ученик на неговата спирка. Автобусът пристига на началната спирка в момент 0. Времето за качване на учениците в автобуса е 0.

Напишете програма school, която минимизира времето за придвижване на автобуса от началната спирка до училището, при условие, че превозва M ученици или всичките, ако общият им брой е по-малък от М.

На първия ред на стандартния вход са записани две цели числа N и М – брой на спирките и брой на местата в автобуса. На всеки от следващите N реда са записани: t_i - времето за придвижване до следващата спирка (за последната спирка – до училището), K_i – брой на учениците, които чакат на тази спирка и K_i, момента за пристигане на учениците в ненамаляващ ред (всички числа са цели).

На един ред на стандартния изход програмата трябва да изведе едно цяло число – минималното време за придвижване на автобуса от началната спирка до училището, като той пристига или пълен, или превозва всички ученици, ако общият им брой е по-малък от М.

• 2 ≤ N*M ≤ 10⁶