Problem Description

A piece is placed at the origin $(0,0)$ on an infinite 2D plane. You have $n$ available movement commands, and each command can be represented by a 2D integer vector. Each command can be executed once or not executed at all. The piece may pass through the same point multiple times, and the direction vectors of two commands may also be the same. Your goal is to make the piece end up as far from the origin as possible in Euclidean distance. What is this maximum distance?

Input Format

The first line contains a positive integer $n$, the number of commands.

The next $n$ lines each contain two integers $x, y$, meaning you can move from $(a,b)$ to $(a+x,b+y)$.

Output Format

Output one integer on a single line: the square of the maximum distance.

5
2 -2
-2 -2
0 2
3 1
-3 1

26

Hint

For $100\%$ of the testdata, $n \le 2 \times 10^5$, and $|x|, |y| \le 10^4$.

Sample Explanation

Translated by ChatGPT 5