시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB573764417.671%

문제

2차원 벡터는 (x, y)와 같이 표현될 수 있다. 이러한 벡터들의 합을 정의할 수 있는데, (x1, y1), (x2, y2), ..., (xn, yn)의 합벡터는 (x1 + x2 + ... + xn, y1 + y2 + ... + yn) 이 된다. 또한 2차원 벡터 하나의 크기를 정의할 수 있는데, 벡터 (x, y)의 크기는 x2 + y2이 된다.

평면상에 N개의 벡터들이 주어져 있다. 이 중에 몇 개를 임의로 골라서, 고른 벡터의 합벡터의 크기를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 벡터의 개수 N(1 ≤ N ≤ 30,000)이 주어진다. 다음 N개의 줄에는 벡터 (x, y)가 주어지는데, x와 y 사이에는 빈칸이 하나 있다. 모든 좌표는 절댓값이 30,000을 넘지 않는 음이 아닌 정수이다. (0, 0)은 입력에서 주어지지 않는다.

출력

최대 합벡터의 크기를 출력한다.

예제 입력 1

9
0 1
6 8
0 -1
0 6
-1 1
-1 2
5 -4
1 0
6 -5

예제 출력 1

360

출처