## Physics Project

View as PDF

Points: 1
Time limit: 2.0s
Memory limit: 256M

Problem types

Burak and Gizem are working on their physics project. They are given $$n$$ 2-dimensional vectors that represent forces and they are required to find the maximum equivalent force possible using a subset of these forces.

Can you help them to find a subset of these vectors so that their sum is the greatest possible?

#### Input

The first line contains a single integer $$n$$. The next $$n$$ lines contain 2 integers each $$x_i$$ and $$y_i$$, the coordinates of the $$i^{th}$$ vector.

• $$1 \le n \le 2 \cdot 10^5$$,
• $$-10^9 \le x_i, y_i \le 10^9$$.

#### Output

Print one integer, the squared length of the longest possible vector Burak and Gizem can create.

#### Example

Input:

4
1 0
0 1
1 1
-1 -1

Output:

8

Input:

7
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Output:

98000000000000000000

#### Explanation

In the first sample, summing up the first three vectors gives vector $$\texttt{2 2}$$ which squared length is 8.