Fișierul intrare/ieșire	muzeu.in, muzeu.out	Sursă	.campion 2009
Autor	Emanuela Cerchez	Adăugată de	Dan Patrick Cristian • danpatrick
Timp de execuție pe test	0.05 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Muzeu(clasa a 6-a)

Muzeul de științe naturale de la noi din oraș oferă posibilitatea organizării lecțiilor de biologie în muzeu. Astăzi au fost programate n grupuri de elevi, astfel încât să nu existe în muzeu două grupuri în același timp. Grupurile sunt numerotate de la 1 la n, în ordinea în care sosesc la muzeu. Toți elevii dintr-un grup vin împreună și pleacă împreună, la terminarea lecției.
La intrarea în muzeu există k dulăpioare în care elevii își pot depozita obiectele personale pe durata vizitării muzeului.
Dimineața toate cele k dulăpioare sunt încuiate. Când un elev vine la lecție, primește cheia de la un dulap, își depozitează obiectele personale în dulap, iar la plecare își la obiectele din dulap și predă cheia. Unii dintre elevi încuie dulapul înainte de a preda cheia, alții îl lasă deschis.
Personalul de la muzeu au observat că în grupul i (1≤i≤n) ai elevi încuie dulapul, în timp ce bi elevi lasă dulapul deschis.
Personalul muzeului dorește să distribuie cheile în așa fel încât la sfârșitul zilei să rămână cât mai multe dulapuri încuiate.

Cerinta

În ipoteza că personalul muzeului distribuie cheile optimal, să se determine care este numărul maxim de dulapuri care rămân închise la sfârșitul zilei.

Date de intrare

Fișierul de intrare muzeu.in conține pe prima linie două numere naturale separate prin spațiu n k, cu semnificația din enunț.
Urmează n linii. Pe linia i+1 sunt scrise două numere naturale ai bi cu semnificația că în grupul i ai elevi închid dulapul, iar bi elevi lasă dulapul deschis.

Date de ieșire

Fișierul de ieșire muzeu.out va conține o singură linie pe care va fi scris un singur număr natural reprezentând numărul maxim de dulapuri care rămân închise la sfârșitul zilei.

Restricții

• 1 ≤ n ≤ 100
• 1 ≤ k ≤ 1000
• 0 ≤ ai ≤ k
• 0 ≤ bi ≤ k
• ai+bi ≤ k

Exemplu

Explicație

Există 4 dulapuri. La muzeu vin două grupuri de elevi. În primul grup elevul 1 încuie dulapul 1, iar elevii 2 și 3 lasă deschise dulapurile 2 și 3.
În al doilea grup, elevul 1 primește cheia de la dulapul 2 pe care îl încuie, iar elevul 2 primește cheia de la dulapul 3 pe care îl lasă deschis.
Prin urmare dulapurile 1, 2, 4 rămân închise.