.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » cafea

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
cafea


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Ion este cel mai apreciat maseur din oras. In fiecare zi, inainte de a se duce la serviciu, Ion se conecteaza la Internet si citeste mail-ul in care secretara firmei anunta programarile existente pentru ziua respectiva. Pentru fiecare persoana programata, este precizat momentul in care va sosi si durata tratamentului solicitat.
Tura lui Ion dureaza N minute. Cand Ion ajunge la serviciu, incepe sa efectueze tratamentele programate. Daca Ion este ocupat atunci cand soseste o persoana programata, persoana va fi preluata de catre colegii lui Ion. Cand termina un tratament, el poate sa bea o cafea, poate citi ziarul etc, pana cand soseste urmatoarea persoana.
Daca exista mai multe persoane care sosesc in acelasi moment, el poate sa aleaga pe oricare dintre ele (restul le va "pasa" colegilor sai). În functie de alegerile facute, Ion poate petrece mai mult timp la cafea sau dimpotriva.

Cerinta

Scrieti un program care sa determine numarul maxim de minute pe care Ion le poate petrece la cafea.

Date de intrare

Prima linie a fisierului de intrare cafea.in contine doua numere naturale N si K, separate prin spatiu, reprezentand durata turei lui Ion, exprimata in minute, respectiv numarul de persoane programate in ziua respectiva.
Fiecare dintre urmatoarele K linii contine informatii despre o persoana programata. Mai exact, pentru o persoana sunt specificate doua numere naturale P si T, separate prin spatiu. Numarul P indica in al catelea minut de la inceputul turei lui Ion soseste persoana respectiva, iar T durata tratamentului, exprimata in minute.

Date de iesire

Fisierul de iesire cafea.out contine o singura linie pe care este afisat numarul maxim de minute pe care Ion le poate petrece la cafea.

Restrictii

  • N <= 10000
  • 1 <= K <= 10000
  • 1 <= P <= N
  • 1 <= P+T-1 <= N

Exemple

cafea.in cafea.out

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

4

 

cafea.in cafea.out

10 6
2 4
2 2
2 1
4 7
8 3
8 1

5

 

cafea.in cafea.out

10 3
1 2
4 3
5 1

5

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Şansa de a deveni campion 2002: adevar, marcare, joc10, prieteni1, bare, soricel1, traseu, zapezi, banda10, soricel2, masina2, excursie1, asmax, salvare, perechi1, culmi, tramvai1, numar2, sume1, raft, bloc, schi, joc12, sediu, soricel3, ferma, fni, sah1, suma3, granita, nr4, fractie, blockout, join, cod3, tunel, lover, trip, pepsi, string, medii, transport, tren3, avion, prime1, poligon1, monkey, premii1, garaj, carti2, gramada, microvirus, tv, gramezi1, puncte2, benzina, aranjari, numere5, fat, izo, top, echipe1, zoo, secvente
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre liste: secvop, rev, cub1, castel, top, coment, urgenta
Software recomandat
surse trimise | ajutor