MVECTOR - Sum of Vectors

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mvector


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


Added by:psetter
Date:2009-03-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 03

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.