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 ≤ 250)
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
hodobox:
20171225 14:49:03
Constraints are incorrect  x,y <= 2500, NOT <= 250. Had to binary search with assert :( 

mahilewets:
20170921 20:13:48
Difference becomes MIN


anurag garg:
20170812 14:28:59
Last edit: 20170813 13:10:59 

akashranjan28:
20170630 10:12:07
@TLE try this.


shloksingh10:
20170629 21:13:14
Nice question mate :D, enjoyed solving it.


heisenberg0820:
20170629 19:25:46
Rainbow Six <3 

TLE:
20170629 15:32:20
can someone provide some tricky cases? Last edit: 20170629 19:53:33 

sas1905:
20170629 05:34:19
It seems Harbinger is winning with the best solution..:P 
Added by:  DJ 
Date:  20170628 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  College contest 