SPOJ Brasil

No ensino médio da América Latina, Klingon se tornou tão popular que muitos dos estudantes começaram a aprender essa língua artificial por conta própria. Após tomar conhecimento da situação, os diretores deciriram implementar cursos formais de Klingon. O problema é que as crianças possuem diferentes níveis iniciais da linguagem. Sendo assim, os diretores decidiram oferecer dois níveis de curso: básico e avançado.

A escola possui diversas divisões, com cada estudante pertencendo a exatamente uma divisão. Devido à burocracia e conflitos de agenda, estudantes de divisões diferentes não podem fazer parte do mesmo curso. Além disso, para ser justo, os níveis básico e avançado devem ser oferecidos a todas as divisões, e ter o mesmo nível de dificuldade em uma divisão.

Sendo assim, cada divisão será particionada em dois grupos: um grupo será associado ao nível básico e o outro grupo ao nível avançado. É possível que uma divisão não possua nenhum estudante em um dos níveis.

Para definir os grupos, um teste de Klingon foi aplicado previamente a todos os estudantes da escola, cada um tirando uma nota entre 0 e 1000, inclusive. Os diretores da escola decidiram que todos os estudantes com uma nota maior ou igual a algum valor T serão matriculados no nível avançado, e todos os estudantes com nota menor que T serão matriculados no nível básico.

No entanto, eles não conseguiram decidir o melhor valor de T. Eles gostariam de um valor que dividisse igualmente todas as divisões. Para isso, eles bolaram uma métrica: eles querem o valor de T que minimize a diferença acumulada, ou seja, a soma da diferença entre o número de estudantes nos dois grupos (básico e avançado) em cada divisão.

Por exemplo, se a escola possui duas divisões, onde uma divisão possui 10 estudantes no nível básico e 20 no nível avançado, enquanto a outra possui 17 e 15, respectivamente, a diferença acumulada seria |10 - 20| + |17 - 15| = 12;

Entrada

A entrada contém vários casos de teste. Cada caso é dado em várias linhas. A primeira linha de cada caso de teste contém um único inteiro N (1 ≤ N ≤ 10⁴), o número de divisões na escola. 2 x N linhas seguem, com cada divisão sendo descrita em duas linhas consecutivas. A primeira linha de cada par contém um único inteiro K_i (1 ≤ K_i ≤ 10⁴), o número de estudantes na divisão i. A segunda linha contém K_i inteiros entre 0 e 1000, inclusive, separados por espaços simples, representando as notas de cada um dos estudantes da divisão i. Você pode assumir que o número total de estudantes em cada caso de teste (ou seja, a soma de todos K_i) não é maior que 10⁵.

O último caso de teste é seguido de uma linha contendo um único zero.

Saída

Para cada caso de teste, imprima uma única linha com um único inteiro representando o menor valor para a diferença acumulada se T for escolhido de forma ótima.

Exemplo

Entrada:
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

Saída:
2
0
2
4