Reggie şi Emoh, deşi buni prieteni, simt mereu nevoia de competiţie. Fascinaţi de vectori, ei au inventat un joc pe această temă. Astfel, se dau 2n vectori, fiecare având extremitatea iniţială în originea sistemului de coordonate cartezian, iar extremitatea finală într-un punct aflat în cadranul I al sistemului cartezian (ambele coordonate pozitive). Astfel, orice vector poate fi reprezentat printr-o pereche de numere a b, reprezentând coordonatele (abscisă, ordonată) a extremităţii sale finale.
Ei aleg pe rând câte un vector, Reggie alegând primul. La sfârşit, fiecare dintre ei va fi ales n vectori. Fiecare dintre ei face modulul sumei vectorilor aleşi, apoi ridică la pătrat acest modul. Numărul rezultat este păstrat ca valoare a jucătorului.

Cerinţă

Scrieţi un program care să maximizeze diferenţa dintre valoarea lui Reggie şi valoarea lui Emoh, ştiind că Emoh joacă în mod optim pentru a minimiza această diferenţă.

Date de intrare

Fişierul de intrare jocv.in conţine pe prima linie numărul natural n reprezentând numărul de vectori pe care trebuie să-i aleagă un jucător. Pe următoarele 2n linii sunt descrişi cei 2n vectori sub forma a două numere naturale pe linie, separate prin spaţii.

Date de ieşire

Fişierul de ieşire jocv.out va conţine o singură linie pe care este scris rezultatul cerut.

Restricţii

• 1 <= n <= 100 000
• 0 <= coordonatele vectorilor <= 32 768
• Atenţie, numărul de vectori ce apar în fişierul de intrare este 2n.
• Rezultatul va intra pe un întreg unsigned pe 64 de biţi.
• Suma vectorilor (a, b) şi (c, d) este vectorul (a + c, b + d). Modulul vectorului (a, b) este valoarea  sqrt(a * a + b * b). Evident, modulul la pătrat al vectorului (a, b) are valoarea a * a + b * b.

Exemple

jocv.in	jocv.out
2 1 1 2 3 3 2 4 6	88

stud. Cătălin-Ştefan Tiseanu

Universitatea Bucureşti

ctiseanu@yahoo.com