Bajtori

Time limit1sMemory limit128 MB

Summary

Select a subset of squares to maximize the sum of the squared red total and squared green total.

Level: Hard8 of 10
Topics: Geometry, Sorting, Two pointers
Solved: No attempts yet

Problem

Recently the Japanese puzzle Bajtori has become very popular in Bajtocja. The game board consists of $n$ squares, and on each square two integers are written: a red number and a green number. The player must choose a subset of the squares so that the weight of the chosen set is as large as possible.

The weight of a set is computed as follows. First, add together the green numbers of all chosen squares and square that sum. Then add together the red numbers of all chosen squares and square that value as well. The weight of the set is the sum of these two squares.

Bajtazar loves Bajtori, but after solving a puzzle he can never tell whether his result is the best possible, so he has asked you for help. Write a program that, for a given puzzle, computes the maximum weight that can be obtained.

Input

The first line contains a natural number $n$ $(1 \le n \le 30000)$ , the number of squares in the puzzle. Each of the next $n$ lines describes one square. Line $i+1$ contains the red number $c$ and the green number $z$ $(-30000 \le c, z \le 30000)$ of the $i$ -th square, separated by a single space.

Output

Print a single natural number: the maximum weight obtainable in the puzzle given on the input.

Examples3

Example 1
Input
```
2
1 1
-1 -1
```
Expected output
```
2
```
Example 2
Input
```
1
3 4
```
Expected output
```
25
```
Example 3
Input
```
2
3 0
0 4
```
Expected output
```
25
```