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) a_i elevi încuie dulapul, în timp ce b_i 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.

Cerinţă

Î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 a_i b_i cu semnificaţia că în grupul i a_i elevi închid dulapul, iar b_i 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 ≤ a_i ≤ k
• 0 ≤ b_i ≤ k
• a_i+b_i ≤ k

Exemple

muzeu.in	muzeu.out	Explicaţii
2 4 1 2 1 1	3	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.

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com