MVECTOR - Sum of Vectors

We can represent a 2D vector as a pair (X, Y). The sum of two or more vectors is a vector whose coordinates are the sums of the corresponding coordinates of all the vectors in the sum. e.g. (1, 2) + (3, 4) + (5, 6) = (1 + 3 + 5, 2 + 4 + 6) = (9, 12) Weight of a vector (x, y) is defined as x * x + y * y. You are given N vectors on a plain.

Your task is to write a program that will determine a subset of those vectors so the weight of the sum of all vectors in that subset is maximal.

Note: Use 64-bit integers (int64 in pascal or long long in c)

Input

In the first line of the input file is an integer N, 1 ≤ N ≤ 30,000, the number of vectors.

The following N lines contain descriptions for each of the vectors. A description is made of two integers X and Y, separated by a single blank, -30,000 ≤ X, Y ≤ 30,000.

None of the given vectors will be (0, 0)

Output

In the first and only line of the output file you have to write the weight of the maximum sum.

Sample

Input:
5
5 -8
-4 2
4 -2
2 1
-6 4

Output:
202
Input:
4
1 4
-1 -1
1 -1
-1 4

Output:
64
Input:
9
0 1
6 8
0 -1
0 6
-1 1
-1 2
5 -4
1 0
6 -5

Output:
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.