După o zi grea de școală, Gigel se joacă GTA (Gigel Troc Auto), jocul său preferat. În acesta trebuie să cumperi mașini de la alți jucători astfel incât să câștigi cât mai mulți bani. Când va intra în joc acesta va avea n cereri de cumpărare (schimb) și b dolari. Jucătorii vând mașini pentru un anumit preț p. Prețul real al acestora este egal cu g. Din păcate, Gigel are un calculator neperformant. Acesta mai are t secunde până când calculatorul său dă crash! Gigel vă roagă să-l ajutați să găsească cea mai bună metodă de a cumpăra automobilele.

Cerința

Știind p, g pentru orice mașină și câți dolari are Gigel, ajutați-l să găsească cea mai mare sumă de bani pe care o poate obține (b + ∑ g - ∑ p) (∑ g = suma valorilor lui g pentru fiecare mașină cumpărată, iar ∑ p = suma valorilor lui p pentru fiecare automobil achiziționat). Desigur, b ≥ ∑ p.

Date de intrare

Fișierul de intrare gta.in conține pe prima linie n, b si t. Pe următoarele n linii vor fi g și p (gi, pi, 1 ≤ i ≤ n).

Date de ieșire

Fișierul de ieșire gta.out conține răspunsul la cerință. Dacă Gigel nu are bani să facă cel puțin un schimb, se va afișa mesajul GIGEL NU ARE BANI.

Restricții și precizări

• 1 ≤ t ≤ n ≤ 500
• 1 ≤ b ≤ 1.000
• 1 ≤ p i, gi ≤ 1.000
• Un schimb durează o secundă.
• Gigel este obligat să cumpere cel puțin o mașină (în cazul în care are destui bani).
• Gigel poate cumpăra cel mult t maşini.
• După finalizarea tuturor achiziționărilor, Gigel va primi toate mașinile plătite.

Exemplul 1:

gta.in

3 100 1
65 50
66 18
391 101

gta.out

148

Explicaţie:

Gigel alege maşina 2.

Exemplul 2:

gta.in

5 100 4
2 10
4 50
400 100
200 50
300 50

gta.out

500

Explicaţie:

Gigel cumpără maşinile 4: (200, 50) şi 5: (300, 50). Suma căutată este egală cu b + ∑ g - ∑ p = 100 + (200 + 300) - (50 + 50) = 500.