BAISED - Biased Standings

Usually, results of competitions are based on the scores of participants. However, we are planning a change for the next year of IPSC. During the registration each team will be able to enter a single positive integer : their preferred place in the ranklist. We would take all these preferences into account, and at the end of the competition we will simply announce a ranklist that would please all of you.

But wait... How would that ranklist look like if it won't be possible to satisfy all the requests?

Suppose that we already have a ranklist. For each team, compute the distance between their preferred place and their place in the ranklist. The sum of these distances will be called the badness of this ranklist.

Problem specification

Given team names and their preferred placements find one ranklist with the minimal possible badness.

Input specification

The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.

Each test case looks as follows: The first line contains N : the number of teams participating in the competition. Each of the next N lines contains a team name (a string of letters and numbers) and its preferred place (an integer between 1 and N, inclusive). No two team names will be equal.

Output specification

For each of the test cases output a single line with a single integer : the badness of the best ranklist for the given teams.

Example

Input:
2

7
noobz 1
llamas 2
Winn3rz 2
5thwheel 1
NotoricCoders 5
StrangeCase 7
WhoKnows 7

3
ThreeHeadedMonkey 1
MoscowSUx13 1
NeedForSuccess 1

Output:
5
3
Explanation:

In the first test case, one possible ranklist with the minimal badness is:

1. noobz
2. llamas
3. Winn3rz
4. 5thwheel
5. NotoricCoders
6. WhoKnows
7. StrangeCase

In the second test case all ranklists are equally good.

Note: the input file will not exceed 5MB.

Added by:Fudan University Problem Setters
Date:2007-12-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:IPSC 2006

hide comments
2013-10-17 15:10:42 aar
Easy Question..
2013-07-18 17:02:51 Raman Shukla
Easy problem... My 100th Classical problem and 2nd in C++...
2013-07-04 08:25:39 achiever202
maximum value of N ??
2013-07-01 17:05:22 BLANKRK
eazzyy.....
2013-05-28 04:41:54 Shivam Bansal
i dont know why i got too much compilation errors.it got accepted at last.It was working fine on my local machine. It was showing stray \302 \244 error. admin please help
2013-04-05 07:22:38 bruce wayne
use long long int for c / cpp
2013-02-14 11:21:21 npsabari
O(NlogN) passed!
2013-01-05 02:26:38 Spar!k


Last edit: 2013-03-24 00:26:01
2012-12-18 14:22:27 张翼德
easy problem....don't bother about team name -_-

Last edit: 2012-12-18 14:23:35
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.