Intr-un show de televiziune N concurenti participa intr-o competie pe viata si pe moarte din care doar unul dintre ei poate iesi castigator. Fiecare concurent a adunat pe parcursul emisiunii un numar de puncte, S[i], si acum urmeaza proba finala. Fiecare dintre ei trebuie sa aleaga una dintre cele doua porti din fata lor. Doar una dintre ele ascunde in spatele ei marele premiu. De asemenea fiecare concurent parieza un numar de puncte P[i](0≤P[i]≤S[i]). Daca poarta pe care a ales-o el este cea care ascunde premiul atunci punctajul sau va fi S[i]+P[i] iar daca nu a ghicit-o S[i]-P[i]. Concurentul cu punctajul maxim in urma acestei probe va castiga marele premiu. Daca exista mai multe punctaje maxime nu va castiga nimeni. Ultimul concurent, cine altul decat Petrica, se afla in fata unei decizii foarte dificile: el stie punctajele celorlalti concurenti si ce numar de puncte au pariat fiecare dar nu stie ce porti au ales acestia, in schimb stie ca fiecare concurent – chiar si el – are 50% sanse sa ghiceasca poarta castigatoare si 50% sanse sa nu o ghiceasca. Trebuie sa decida ce numar de puncte va paria pentru ca probabilitatea sa de castig sa fie cat mai mare (chiar daca pentru doua moduri de a paria probabilitatile sunt foarte apropiate, diferenta fiind practic nula, Petrica va alege modul pentru care probabilitatea sa de castig este mai mare).

Cerinta

Calculati numarul de puncte pe care trebuie sa-l parieze Petrica pentru a avea sanse de castig cat mai mari. Daca exista mai multe solutii alegeti-o pe cea mai mica. De asemenea aflati si probabilitea maxima de castig pe care o poate avea Petrica.

Date de intrare

Fisierul tvshow.in va contine pe prima linie numarul intreg N reprezentand numarul de concurenti din concurs. Fiecare din urmatoarele N – 1 linii va contine doi intregi separati printr-un spatiu reprezentand scorul si numarul de puncte pariate pentru fiecare din primii N – 1 concurenti. Ultima linie contine un singur numar intreg reprezentand scorul lui Petrica.

Date de iesire

Pe prima linie a fisierului tvshow.out se va afla numarul de puncte pariat de Petrica. Pe urmatoarele doua linii se vor afla doua numere intregi A si B care reprezinta probabilitatea maxima de castig a lui Petrica sub forma de fractie ireductibila (probabilitatea este egala cu A/B.

Restrictii

• 1 < N < 301
• Valorile scorurilor sunt numere intregi din intervalul [0, 30000]
• Pentru 40% din teste N <= 17

Exemple

Silviu Ionut Ganceanu
Universitatea Politehnica Bucuresti
Contact: tzi_ganci at hotmail dot com