== include(page="template/taskheader" task_id="gramezi") ==
Poveste si cerinta...
Zaharel si Bronzarel joaca urmatorul joc: se pun pe masa $N$ gramezi de monede. Se stie ca daca Zaharel ia gramada $i$ primeste $A{~i~}$ din monedele din gramada, iar daca Bronzarel ia gramada $i$ primeste $B{~i~}$ din monedele din gramada (se stie ca fiecare gramada are cel putin $max(A{~i~}, B{~i~})$ monede iar monedele care raman se arunca). Cei doi jucatori iau alternativ cate o gramada, pana cand se epuizeaza toate cele $N$, iar Zaharel este primul care ia o gramada. La final, castiga jucatorul cu mai multe monede. Daca cantitatile de monede sunt egale, jocul se considera remiza.
Stiind ca Zaharel si Bronzarel joaca optim, determinati numarul de monede pe care il va avea fiecare jucator la final. Prin joc optim se intelege ca fiecare jucator incearca sa mareasca diferenta dintre numarul de monezi pe care le detine si numarul de monezi ale celuilalt jucator, iar in cazul in care are mai multe posiblitati de a obtine aceeasi diferenta va incerca sa-si mareasca numarul de monede.
h2. Date de intrare
...
Pe prima linie a fisierului de intrare $gramezi.in$ este scris numarul natural $N$. Pe urmatoarele $N$ linii se vor gasi cate doua numere naturale separate prin cate un spatiul, reprezentand valorile $A{~i~}$, respectiv $B{~i~}$.
h2. Date de iesire
...
Prima linie a fisierului $gramezi.out$ va contine doua numere naturale separate prin spatii reprezentand scorul lui Zaharel, respectiv scorul lui Bronzarel.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 30.000$
* $1 ≤ A{~i~}, B{~i~} ≤ 30.000$
h2. Exemplu
table(example). |_. gramezi.in |_. gramezi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
2 10
5 5
7 3
4 1
| 9 6
|
h3. Explicatie
...
Zaharel ia gramada 1, apoi Bronzarel ia gramada 2, apoi Zaharel ia gramada 3, apoi Bronzarel ia gramada 4. O alta posiblitate de joc cu aceeasi diferenta de scor este urmatoarea: Zaharel ia gramada 1, apoi Bronzarel ia gramada 3, apoi Zaharel ia gramada 2, apoi Bronzarel ia gramada 4. Astfel, s-ar fi obtinut scorurile 7, respectiv 4, dar acestea sunt mai mici decat in prima varianta.
== include(page="template/taskfooter" task_id="gramezi") ==
