Bajtori

최근 Bajtocja에서 일본식 퍼즐 Bajtori가 큰 인기를 끌고 있다. 게임판은 $n$개의 칸으로 이루어져 있으며, 각 칸에는 정수 두 개, 곧 빨간 수와 초록 수가 적혀 있다. 플레이어는 칸들의 부분집합을 골라 그 집합의 무게가 최대가 되도록 만들어야 한다.

집합의 무게는 다음과 같이 계산한다. 먼저 고른 칸들의 초록 수를 모두 더한 뒤 그 합을 제곱한다. 다음으로 고른 칸들의 빨간 수를 모두 더한 뒤 그 값도 제곱한다. 이 두 제곱의 합이 고른 집합의 무게이다.

Bajtazar는 Bajtori를 무척 좋아하지만, 퍼즐을 풀고 나서도 자신이 얻은 결과가 가능한 최선인지 알 수 없어 당신에게 도움을 청했다. 주어진 퍼즐의 설명에 대해 얻을 수 있는 최대 무게를 계산하는 프로그램을 작성하여라.

첫째 줄에 퍼즐의 칸 수를 나타내는 자연수 $n$ $(1 \le n \le 30000)$이 주어진다. 이어지는 $n$개의 줄에는 각 칸의 정보가 주어진다. $i+1$번째 줄에는 $i$번째 칸의 빨간 수 $c$와 초록 수 $z$ $(-30000 \le c, z \le 30000)$가 공백으로 구분되어 주어진다.

첫째 줄에 입력으로 주어진 퍼즐에서 얻을 수 있는 최대 무게를 한 개의 자연수로 출력한다.