Cerință
Se dau n grupe de dansatori, numerotate de la la . Fiecare grupă formează o horă și este alcătuită dintr-un număr dat de fete și un număr dat de băieți.
Dorim să "unim" două hore, astfel încât în cea rezultată diferența (în valoare absolută) dintre numărul de fete și numărul de băieți să fie minimă. Dacă avem mai multe variante care minimizează această valoare, ne dorim să obținem o horă formată din cât mai multe persoane.
Date de intrare
Pe prima linie a fișierului de intrare hora.in se găsește valoarea . Pe fiecare dintre următoarele linii se află câte două numere întregi, și , separate prin spațiu, reprezentând numărul de fete respectiv numărul de băieți dintr-o grupa (horă).
Date de ieșire
Pe prima linie a fișierului de ieșire hora.out se vor găsi cele două numere care caracterizează hora formată. Primul număr este diferența minimă (în valoare absolută). Al doilea număr reprezintă numărul de dansatori (maxim posibil pentru diferența minimă determinată).
Restricții și precizări
- ;
- ;
- pentru orice horă dată + este un număr nenul;
- pentru teste în valoare de 37 de puncte avem ;
Exemplul 1
hora.in
3
1 2
4 2
3 1
hora.out
1 9
Explicație
Unind primele două hore vom obține una formată din persoane dintre care fete și băieți, deci cu diferența acestor numere (considerată în valoare absolută) egală cu .
Exemplul 2
hora.in
3
1 4
2 4
5 7
hora.out
4 18
Explicație
Unind hora a doua și a treia obținem una cu danatori, fete și băieți.