토너먼트

매년 9월, 루워터(Loowater) 왕국은 마상 창시합 토너먼트를 연다. 각 경기에서는 두 기사가 서로를 말에서 떨어뜨리려 겨룬다. 이긴 기사는 다음 경기로 올라가고, 진 기사는 탈락한다. 이 과정을 반복하여 마지막에 한 명의 기사만 남으면 그 기사가 우승자가 된다.

대진은 기사 수 $k$에 대해 우승에 필요한 경기 수가 가능한 최소값 $e$(즉 $e = \lceil \log_2 k \rceil$)를 넘지 않도록 짜인다. 이런 대진을 만들려면 일부 기사는 1라운드를 치르지 않아야 하며, 이런 기사는 부전승(bye)을 받았다고 한다. 정확히 $2^e - k$명의 기사가 부전승을 받고, 나머지 기사들은 1라운드에서 맞붙을 짝으로 나뉜다.

1라운드는 각 짝을 이루는 두 기사의 능력치가 비슷할수록 더 흥미롭다. 능력치가 각각 $a$, $b$인 두 기사로 이루어진 짝의 부조화도(mismatch)를 $(a-b)^2$으로 정의한다. 어떤 기사에게 부전승을 줄지, 그리고 나머지를 어떻게 짝지을지를 정하여 1라운드의 모든 짝에 대한 부조화도의 합이 최소가 되도록 하라. 그 최소 부조화도 합을 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 기사 수를 나타내는 정수 $k$($2 \le k \le 2500$)가 주어진다. 이어지는 $k$개의 줄에는 각 기사의 이름과 능력치가 공백으로 구분되어 주어진다. 이름은 길이가 20 이하인 영소문자 문자열이고, 능력치는 $0 \le \text{ability} \le 10^6$을 만족하는 정수이다. 입력은 $0$ 하나만 있는 줄로 끝나며, 이 줄은 테스트 케이스가 아니므로 처리하지 않는다.

각 테스트 케이스마다 1라운드 부조화도 합의 최솟값을 한 줄에 출력하라. 여기서 능력치가 $a$, $b$인 짝의 부조화도는 $(a-b)^2$이고, 합은 1라운드의 모든 짝에 대한 총합이다.