클링온어 반 편성

라틴 아메리카의 한 고등학교에서 클링온어가 큰 인기를 끌면서, 많은 학생이 스스로 이 인공어를 공부하기 시작했다. 이를 알게 된 학교는 정식 클링온어 수업을 개설하기로 했다. 학생마다 이미 알고 있는 수준이 제각각이므로, 수업은 기초반과 심화반 두 단계로 나누어 운영한다.

학교는 여러 개의 분반(division)으로 구성되어 있으며, 모든 학생은 정확히 하나의 분반에 속한다. 시간표 문제로 서로 다른 분반의 학생은 같은 클링온어 수업을 들을 수 없다. 또한 공정성을 위해, 모든 분반에 대해 기초반과 심화반을 같은 난이도로 제공해야 한다.

따라서 각 분반은 두 그룹으로 나뉜다. 한 그룹은 기초반 수업을, 다른 그룹은 심화반 수업을 듣는다. 어떤 분반은 두 단계 중 한쪽에 학생이 한 명도 없을 수도 있다.

모든 학생은 이미 클링온어 배치 시험을 보았고, $0$ 이상 $1000$ 이하의 정수 점수를 받았다. 학교는 하나의 기준값 $T$를 정한다. 점수가 $T$ 이상인 학생은 모두 심화반에, 점수가 $T$ 미만인 학생은 모두 기초반에 배정된다.

학교는 분반들을 최대한 고르게 나누는 $T$를 원한다. $T$가 정해지면 각 분반은 그 분반의 기초반 학생 수와 심화반 학생 수의 차이(절댓값)를 기여한다. 이 값들을 모든 분반에 대해 더한 것을 누적 차이라고 한다.

예를 들어 학교에 두 분반이 있다고 하자. 첫 번째 분반에는 기초반 $10$명, 심화반 $20$명이 있고, 두 번째 분반에는 기초반 $17$명, 심화반 $15$명이 있다. 그러면 누적 차이는 $|10 - 20| + |17 - 15| = 12$이다.

누적 차이가 최소가 되도록 $T$를 선택하라.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 학교의 분반 수를 나타내는 정수 $N$ ($1 \le N \le 10^4$)이 주어진다. 이어서 $2N$개의 줄이 주어지며, 두 줄씩 한 분반을 설명한다. 분반 $i$에 대해, 두 줄 중 첫 줄에는 그 분반의 학생 수를 나타내는 정수 $K_i$ ($1 \le K_i \le 10^4$)가, 둘째 줄에는 그 학생들의 점수인 $0$ 이상 $1000$ 이하의 정수 $K_i$개가 공백 하나로 구분되어 주어진다. 한 테스트 케이스 안의 학생 수 총합(모든 $K_i$의 합)은 $10^5$을 넘지 않는다.

마지막 테스트 케이스 다음에는 $0$ 하나만 있는 줄이 주어진다.

각 테스트 케이스마다, $T$를 최적으로 선택했을 때 가능한 최소 누적 차이를 정수 하나로 한 줄에 출력한다.