Nosaukums
Strādnieku autobuss (bus2)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
67%

Definīcija

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 raksturojums

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 raksturojums

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


Piezīmes

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


Paraugdati

Stdin
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4
Stdout
4

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.