Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KLINGON - Níveis de Klingon

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 ≤ 104), 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 Ki (1 ≤ Ki ≤ 104), o número de estudantes na divisão i. A segunda linha contém Ki 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 Ki) não é maior que 105.

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


Adicionado por:Wanderley Guimarăes
Data:2011-03-07
Tempo limite:0.823s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Final Sul-Americana da Maratona de Programação da ACM 2009

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.