Dienesta autobuss veic reisu pa noteiktu maršrutu un, gadījumā, ja tajā ir brīvas vietas, uzņem strādniekus, kas gaida pieturās, lai aizvestu tos uz rūpnīcu. Autobuss var arī pagaidīt vēl neatnākušos strādniekus pieturā. Ir zināms kad katrs strādnieks atnķ pieturā, kā arī laiks, kāds nepieciešams autobusam, lai aizbrauktu no vienas pieturas līdz nākamai. Pirmajā pieturā autobuss atbrauc laika momentā 0. Uzskatiet, ka strādnieku iekāpšana laiku neprasa.

Uzrakstiet programmu, kas nosaka mazāko laiku, kāds nepieciešams, lai autobuss aizvestu lielāko iespējamo strādnieku skaitu! 

Ievaddatu pirmā rinda satur divus naturālus skaitļus - pieturu skaitu N 1 <=N <= 200000, un vietu skaitu autobusā M 1<=M<=2000. Skaitļi atdalīti ar tukšumsimbolu.
Katra i-tā no nākošajām N faila rindām satur veselu skaitli - laiks, kāds nepieciešams, lai aizbrauktu no i-tās līdz i+1-ajai pieturai (N+1-ā pietura ir rūpnīca), strādnieku skaitu K, kuri atnāk uz i-to pieturu un katra strādnieka atnākšanas brīdis viņu atnākšanas secībā.

Izvaddatu vienīgajā rindā jāizvada mazākais laiks, kāds nepieciešams, lai autobuss aizvestu lielāko iespējamo strādnieku skaitu.

Uzdevums izmantots Ukrainas XIII informātikas olimpiādē 2000.gadā.