apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

bus2 Strādnieku autobuss 1 sek.


 Uzdevums

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!

 
 Ievaddati

Teksta faila bus2.in 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ā.

 
 Izvaddati

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

 
 Piemērs

bus2.inbus2.out
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4
4

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

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS