MVECTOR - Sum of Vectors

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


Được gửi lên bởi:~!(*(@*!@^&
Ngày:2009-03-22
Thời gian chạy:0.213s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:COI 03

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