Tournament

Interview

Time limit1sMemory limit128 MB

Summary

Given k knights with abilities, choose 2^e - k of them to sit out the first round and pair the rest to minimize the sum of squared ability differences.

Level: Medium6 of 10
Topics: Dynamic programming, Sorting, Math, Greedy
Solved: No attempts yet

Problem

Every September, the Kingdom of Loowater holds a jousting tournament. In each event a pair of knights attempt to knock each other from their horses. The winning knight advances to the next event, while the loser is eliminated. This continues until a single knight remains; that knight is declared champion.

The schedule is arranged so that no knight has to compete in more than $e$ events to become champion, where $e$ is the smallest value possible for the given number of knights $k$ (that is, $e = \lceil \log_2 k \rceil$ ). To build such a schedule, some knights must sit out the first round; such a knight is said to be awarded a bye. Exactly $2^e - k$ knights are awarded a bye, and the remaining knights are split into pairs for the first round.

The first round is more interesting when the two knights in each pair are as evenly matched as possible. The mismatch of a pair whose abilities are $a$ and $b$ is defined to be $(a-b)^2$ . Decide which knights receive a bye, and how to pair the rest, so that the total mismatch summed over all first-round pairs is as small as possible. Report that minimum total mismatch.

Input

The input consists of several test cases. Each test case begins with a line containing an integer $k$ ( $2 \le k \le 2500$ ), the number of knights. Each of the next $k$ lines contains the name and the ability of one knight, separated by a space. A name is a string of at most 20 lowercase letters; an ability is an integer with $0 \le \text{ability} \le 10^6$ . The input ends with a line containing a single $0$ , which is not a test case and must not be processed.

Output

For each test case, output a single line containing the minimum possible total mismatch, where the mismatch of a first-round pair with abilities $a$ and $b$ is $(a-b)^2$ and the total is the sum over all first-round pairs.

Examples3

Example 1

Input

3
gallahad 10
lancelot 11
mccartney 2
0

Expected output

Example 2
Input
```
2
arthur 5
bedivere 8
0
```
Expected output
```
9
```
Example 3
Input
```
4
will 1
xavier 2
yusuf 10
zoe 12
0
```
Expected output
```
5
```