시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 323 22 13 15.663%

문제

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

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

입력

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

출력

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

예제 입력

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

예제 출력

360

힌트

출처