|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
K - Klingon Levels
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
In a Latin American high school, the klingon language has become so popular that many of the students have begun learning this artificial language on their own. After becoming aware of the situation, the directors have decided to implement formal klingon courses. The problem is that kids have different starting levels of knowledge of the language. Therefore, the directors decided to offer two course levels: basic and advanced.
The school has several divisions, with each student belonging to exactly one division. Because of bureaucracy and schedule conflicts, students of different divisions cannot be in the same klingon course. Also, to be fair, the basic and advanced klingon levels should be offered to all divisions, and have the same level of difficulty among the divisions.
Therefore, each division will be partitioned into two groups: one group will be assigned a basic level course, and the other group an advanced level course. It is possible, also, that a division does not contain any students in one of the levels.
To assign the levels, a klingon test has been previously taken by all students of the school, each getting an integer grade between $0$ and $1000$, inclusive. To accomplish the aforementioned goals, the school directors have decided that all students with a score greater than or equal to some $T$ will be assigned the advanced level, and all students with a score less than $T$ will be assigned the basic level.
However, they cannot decide on the best value of $T$. They would like a value that evenly splits all divisions. For this, they came up with a metric: They want the value of $T$ that minimizes the accumulated difference, that is, the sum of the difference between the number of students in the two groups (basic and advanced) within each division.
For example, if the school has two divisions, where one division has $10$ students in the basic level and $20$ in the advanced level, while the other one has $17$ and $15$, respectively, the accumulated difference would be $|10 - 20| + |17 - 15| = 12$.
Input
There are several test cases. Each test case is given in several lines. The first line of each test case contains a single integer $N$ $(1 \leq N \leq 10^4)$, the number of divisions in the school. $2 \times N$ lines follow, with each division being described in two consecutive lines. The first line of each group of two contains a single integer $K_i$ $(1 \leq K_i \leq 10_4)$ the number of students in division $i$. The second line contains $K_i$ integers between $0$ and $1000$, inclusive, separated by single spaces, representing the scores of each of the students in division $i$. You may assume that the total number of students within each test case (that is, the sum of the values of all $K_i$) is not greater than $10^5$.
The last test case is followed by a line containing a single zero.
Output
For each test case, output a single line with a single integer representing the minimum value for the accumulated difference if $T$ is chosen optimally.
Sample test(s)
Input
2
2
1 2
2
3 4
2
2
1 4
2
2 3
3
4
1 10 100 1000
3
5 55 555
5
4 16 64 256 1000
1
4
500 500 500 500
0
Output
2
0
2
4