시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB7913925.714%

문제

W punkcie (0, 0) nieskończonej kratki stoi pionek. Pionek ma n dozwolonych ruchów. Każdy z nich jest opisany za pomocą wektora o współrzędnych całkowitych. Pionek może każdy z ruchów wykonać co najwyżej raz, w dowolnej kolejności. Wektory opisujące ruchy mogą się powtarzać i wtedy pionek może wykorzystać każdy z nich.

Naszym celem jest dostać się pionkiem do punktu położonego możliwie najdalej od punktu początkowego (w odległości euklidesowej). Jak daleko może on dotrzeć?

입력

Pierwszy wiersz standardowego wejścia zawiera jedną dodatnią liczbę całkowitą n oznaczającą liczbę możliwych ruchów pionka. Każdy z kolejnych n wierszy zawiera dwie liczby całkowite xi, yi (−104 ≤ xi, yi ≤ 104) oddzielone pojedynczym odstępem i oznaczające wektor [xi, yi] opisujący możliwy ruch pionka.

출력

Twój program powinien wypisać na standardowe wyjście liczbę całkowitą oznaczającą kwadrat odległości od punktu (0, 0) do najdalszego punktu, do którego może doskoczyć pionek.

제한

  • n ≤ 200 000

예제 입력 1

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

예제 출력 1

26

힌트

Wyjaśnienie do przykładu: Na rysunku przedstawiono rozwiązanie optymalne wykorzystujące ruchy opisane wektorami [0, 2], [3, 1] oraz [2, −2]. Inne, równie dobre rozwiązanie uzyskujemy za pomocą wektorów [0, 2], [−3, 1] oraz [−2, −2].