Nosaukums
Darbu saraksts (darbi)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

Katru dienu pirms došanās uz darbu Mirko pārbauda savu e-pastu. Viņa priekšnieks katru rītu atsūta darbu sarakstu, ko Mirko šajā dienā varētu darīt. Katram darbam ir norādīts sākuma laiks un ilgums.

Mirko darbadiena ilgst N minūtes. Pēc ierašanās darbā, Mirko sāk darbu izpildi pēc priekšnieka atsūtītā saraksta. Ja sarakstā ir vairāki darbi ar vienu un to pašu sākuma laiku, Mirko var izvēlēties, kuru no tiem pildīt. Citus darbus padarīs Mirko kolēģi. Ja Mirko ir pabeidzis vienu darbu un līdz nākošā darba sākumam vēl ir atlicis laiks, tad Mirko var atpūsties un palasīt jaunākās avīzes. Ja Mirko ir brīvs un ir pienācis jauna darba sākuma brīdis, Mirko pienākums ir sākt to pildīt (vai vienu no tiem, ja ir izvēle). Ja pēc saraksta ir pienācis kāda darba sākuma laiks, bet Mirko ir aizņemts ar cita darba izpildi, tad Mirko turpina darīt jau iesākto darbu un viņam nebūs jadara šis darbs pat tad, kad iesāktais būs pabeigts.

Brīžos, kad vairāki darbi sākas vienlaicīgi, Mirko veicamo darbu var izvēlēties tā, ka laikrakstu lasīšanai paliek vairāk laika.

Uzrakstiet programmu, kas nosaka, kādu lielāko kopējo brīvā laika daudzumu Mirko dotajā dienā var sev sagādāt!


Ievaddatu raksturojums

Izvaddatu pirmajā rindā dotas divu naturālu skaitļu N(darba dienas ilgums minūtēs, 1≤N≤10000) un K(darbu skaits, 1≤K≤10000) vērtības, kas atdalītas ar tukšumsimbolu.

Katrā no nākošajām K faila rindām dots viena darba apraksts - divu naturālu skaitļu P un T vērtības, kas atdalītas ar tukšumsimbolu. Šie skaitļi norāda, ka darbs sākas P-tajā minūtē un tā ilgums ir T minūtes. Zināms, ka 1≤P≤N, 1≤P+T-1≤N.


Izvaddatu raksturojums

Ievaddatu vienīgajā rindā jāizvada Mirko brīvā laika lielākais iespējamais ilgums.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2002.gadā


Paraugdati

Stdin
10 3
1 2
4 3
5 1
Stdout
5

Stdin
10 6
2 4
2 2
2 1
4 7
8 3
8 1
Stdout
5

Stdin
15 6
1 2
1 6
4 11
8 5
8 1
11 5
Stdout
4

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