УЧИЛИЩЕН АВТОБУС
시간 제한1초메모리 제한1024 MB
정원 M인 버스가 정해진 노선의 정류장들을 지나며 각 정류장에 도착하는 학생들을 태운다. 기다릴 수 있을 때 M명(전체가 더 적으면 전부)을 태우고 학교에 도착하는 최소 시간을 구한다.
문제
Училищен автобус може да вози най-много М ученици. Авобусът всеки ден вози ученици до училището по установен маршрут, който включва няколко спирки. На всяка спирка в атобуса се качват ученици, ако има свободни места. Също автобусът може да чака на спирката ученици, които все още не са дошли. Известни са времената за придвижване на автобуса от една спирка до следващата, както и моментите на пристигане на всеки ученик на неговата спирка. Автобусът пристига на началната спирка в момент 0. Времето за качване на учениците в автобуса е 0.
Напишете програма school, която минимизира времето за придвижване на автобуса от началната спирка до училището, при условие, че превозва M ученици или всичките, ако общият им брой е по-малък от М.
입력
На първия ред на стандартния вход са записани две цели числа N и М – брой на спирките и брой на местата в автобуса. На всеки от следващите N реда са записани: ti - времето за придвижване до следващата спирка (за последната спирка – до училището), Ki – брой на учениците, които чакат на тази спирка и Ki, момента за пристигане на учениците в ненамаляващ ред (всички числа са цели).
출력
На един ред на стандартния изход програмата трябва да изведе едно цяло число – минималното време за придвижване на автобуса от началната спирка до училището, като той пристига или пълен, или превозва всички ученици, ако общият им брой е по-малък от М.
제한
- 2 ≤ N*M ≤ 106