Giải bài trực tuyến

Vector được biểu diễn bởi 1 cặp (X,Y). Tổng các vecto là tổng các thành phần tương ứng. e.g. (1,2)+(3,4)+(5,6) = (1+3+5,2+4+6) = (9,12) Khối lượng vecto (x,y) là x*x+y*y. Cho N vecto, tìm một tập con mà tổng của chúng có khối lượng lớn nhất. Kết quả là số 64 bit.

Input

Dòng đầu là N, 1 ≤ N ≤ 30,000, số vector. N dòng tiếp theo là N vecto (X,Y) -30,000 ≤ X,Y ≤ 30,000. Không có vector nào là (0,0)

Output

Ghi khối lượng lớn nhất tìm được

Sample

suma.in 
 
5 
5 -8 
-4 2 
4 -2 
2 1 
-6 4 
 
suma.out 
 
202 

suma.in 
 
4 
1 4 
-1 -1 
1 -1 
-1 4 
 
suma.out 
 
64

suma.in 
 
9 
0 1 
6 8 
0 -1 
0 6 
-1 1 
-1 2 
5 -4 
1 0 
6 -5 
 
suma.out 
 
360