R6PL - Harbinger vs Sciencepal


Rainbow 6 is a very popular game in colleges. There are 2 teams, each having some members and the 2 teams play some matches against each other. The team which wins the maximum number of matches wins the game! Two of my friends Ashank and Aditya (better known as Harbinger and Sciencepal) are great gamers and they want to compete. So they decide to form their own teams.

There are 2*N players who are interested to be a part of their team. Each player has some rating (based on his performance) and Akarsh (Nimbus) is responsible for forming their teams. Being a good friend of both, he wants to form two teams such that the difference of total ratings of the players between the teams becomes minimum. The players come to him in pairs and he has to put one of them in Harbinger's team and the other in Sciencepal's team at that instant. This is a tedious task for him and therefore he needs your help!

Input

The first line of the input contains an integer T denoting the number of the test cases. (1 ≤ T ≤ 10)

First line of each test case contains a number N denoting the number of pair of players. (1 ≤ N ≤ 200)

Next N lines contains rating of the persons in pairs as x and y. (0 ≤ x, y ≤ 2500)

Output

For each test case, print a single integer denoting the minimum possible absolute rating difference between Sciencepal's and Harbinger's team.

Example

Input:

1
2
2 3
4 5

Output: 0

hide comments
Rafail Loizou: 2021-02-19 17:29:28

just be careful when coding. the solution is very simple, consider how small 2500 is and you got this.

Shubham Jadhav: 2020-07-15 18:55:31

-1 for mentioning the incorrect constraints. As mentioned by hodobox, it is 2500 and not 250

kshubham02: 2019-12-13 10:46:38

Slightly misleading problem statement : "... and the other in Sciencepal's team at that instant".
If they are coming in pairs and you have to put them there "at that instant" (without the knowledge of other pairs), then it is impossible to reach an optimum value.
Rather, the statement should say that you have prior knowledge of all the pairs and you want to reach the optimum value (which is the correct assumption in this problem).

hodobox: 2017-12-25 14:49:03

Constraints are incorrect - x,y <= 2500, NOT <= 250. Had to binary search with assert :(

mahilewets: 2017-09-21 20:13:48

Difference becomes MIN
Not sum of absolute values
DIFFERENCE
So the true solution is to make the difference as much negative as possible
UPDATE:
Excuse me, actually there IS a word "absolute"
So the statement is OK
Sorry
I did not noticed

Last edit: 2017-09-22 06:02:42
akashranjan28: 2017-06-30 10:12:07

@TLE try this.
1
4
2 3
5 4
1 3
2 6
output : 0
nice problem dj !

shloksingh10: 2017-06-29 21:13:14

Nice question mate :D, enjoyed solving it.
and concept story was amazing .
more importantly Rainbow Six <3

heisenberg0820: 2017-06-29 19:25:46

Rainbow Six <3

TLE: 2017-06-29 15:32:20

can someone provide some tricky cases?

Last edit: 2017-06-29 19:53:33
sas1905: 2017-06-29 05:34:19

It seems Harbinger is winning with the best solution..:P


Added by:DJ
Date:2017-06-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:College contest