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

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