Un vector se poate reprezenta în plan ca o pereche (X, Y). Suma a doi sau mai multi vectori este un vector ale carui coordonate sunt sumele coordonatelor corespondente din vectorii care se aduna.
De exemplu

(1, 2)+(3, 4)+(5, 6) = (1+3+5, 2+4+6) = (9, 12)

Ponderea unui vector (X, Y) este definita ca X*X+Y*Y.
Se considera N vectori în plan.

Cerinta
Scrieti un program care sa determine o submultime de vectori dintre cei N dati astfel încât ponderea sumei vectorilor din submultime sa fie maxima.

Date de intrare
Prima linie a fisierului de intrare vectori.in contine un numar natural N, care reprezinta numarul de vectori. Fiecare dintre urmatoarele N linii contine descrierea unui vector, ca o pereche de numere întregi separate printr-un spatiu X Y.

Date de iesire
Fisierul de iesire vectori.out contine ponderea sumei vectorilor din submultime (maxima).

Restrictii si precizari

• 1<=N<=30 000
  
• -30 000 <=X, Y <= 30 000
  
• Nici unul dintre vectori nu va fi (0, 0)
  
• Utilizati în calcule întregi pe 64 de biti

Exemple

Timp maxim de executie/test: 0.1 secunde

prof. Marinel Serban
Liceul de Informatica "Gr. C. Moisil" Iasi
e-mail: marinel_serban@yahoo.com