Bajtori

시간 제한1초메모리 제한128 MB

요약

빨간 수 합과 초록 수 합의 제곱을 더한 값이 최대가 되도록 칸들의 부분집합을 선택합니다.

난이도: 어려움10점 중 8점
유형: 기하, 정렬, 투 포인터
정답자: 아직 제출이 없습니다

문제

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

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

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

입력

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

출력

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

예제3

예제 1
입력
```
2
1 1
-1 -1
```
예상 출력
```
2
```
예제 2
입력
```
1
3 4
```
예상 출력
```
25
```
예제 3
입력
```
2
3 0
0 4
```
예상 출력
```
25
```