Priprava naloge

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 128 MB
Avtor:
  • Vid Kocijan
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

S prijatelji organizirate programersko tekmovanje. Razdelili ste si delo in vsi ste pripravili kvalitetne naloge, razen enega od prijateljev, ki ni opravil svojega dela in ne odgovori na nobeno elektronsko pošto. Danes je zadnji dan pred tekmovanjem in prisiljeni ste opraviti delo namesto njega, saj bo tekmovanje sicer polomija.

Prav ta dan imate nabito poln urnik in zavoljo prijateljeve malomarnosti boste morali izpustiti nekaj dogodkov. Bolj konkretno, ta dan imate n dogodkov, ki si sledijo eden za drugim (torej, ko se eden konča, se drugi takoj začne). Dogodki zapolnijo vaš celoten delovnik (pred začetkom prvega in po koncu zadnjega nimate časa za pripravo naloge). Dogodek i traja t_i časovnih enot in ima pomembnost c_i. Kolikšna je najvišja vsota pomembnosti dogodkov, ki se jih lahko udeležite, da imate vmes vseeno dovolj časa, da uspešno pripravite nalogo? Vsakega dogodka se lahko udeležite le v celoti. Če nanj zamudite, ali pa z njega predhodno odidete, štejemo, kot da se ga niste udeležili. Za pripravo naloge potrebujete k strnjenih časovnih enot. Ne morete je pripraviti na pol, se udeležiti kakšnega dogodka, drugo polovico pa pripraviti kasneje, saj bi ti dogodki vmes razbili koncentracijo, ki jo potrebujete za pripravo naloge.

Naloga

Napišite program, ki prebere podatke o vašem urniku in izpiše, kolikšna je največja možna vsota pomembnosti dogodkov, ki se jih lahko udeležite, če boste vmes porabili k zaporednih časovnih enot za pripravo naloge. Če za pripravo naloge ni dovolj časa, izpišite niz Tekma bo polom.

Vhodni podatki

V prvi vrstici se nahajata s presledkom ločeni števili k in n. Nato sledi n vrstic. V i-ti vrstici sta podani s presledkom ločeni števili t_i in c_i.

Omejitve vhodnih podatkov

  • 1 \leq n \leq 10^5
  • 1 \leq c_i,t_i \leq 10^9
  • 1 \leq k \leq 10^9

Izhodni podatki

Vaš program naj izpiše eno število, tj. maksimalno vsoto pomembnosti dogodkov, ki se jih lahko udeležite.

Primeri

Vhod

5 4
2 5
1 6
3 1
3 10

Izhod

11

Vhod

10 2
2 1
3 3

Izhod

Tekma bo polom

Komentar

Pri prvem testnem primeru se nam najbolj splača izpustiti zadnja dva dogodka, vsota pomembnosti prvih dveh dogodkov pa je 11.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task