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.|

GOLSMG - Gols!

A CBF (Companhia Brasileira do Faz-de-conta) criou um novo campeonato nacional que irá substituir a partir de 2012 os campeonatos estaduais.

Cansada do sistema de pontuação convencional, adotado nos campeonatos em todo o mundo, em que a vitória vale 3 pontos, o empate 1 ponto e a derrota 0 pontos, a CBF decidiu inovar e criou um novo sistema de pontuação em que o número de pontos de cada equipe é calculado exclusivamente em função da sequência formada pelo número de gols marcados nas suas partidas, não importando o resultado destas.

No novo campeonato, cada time joga P partidas p1, p2, ..., pP, que são agrupadas em janelas sobrepostas de J partidas. A i-ésima janela é formada pelas partidas {pi, pi+1, ..., pi+J-1}. Assim, a primeira janela do campeonato corresponde às partidas {p1, p2, ..., pJ}, a segunda janela corresponde às partidas {p2, p3, ..., pJ+1}, e assim por diante, totalizando P-J+1 janelas no campeonato.

Sejam g1, g2, ..., gJ os gols marcados por uma equipe em uma determinada janela do campeonato. A pontuação da equipe nessa janela é dada por min{g1, g2, ..., gJ} + max{g1, g2, ..., gJ}, ou seja, a soma dos números mínimo e máximo de gols que a equipe fez nas partidas correspondentes àquela janela. A pontuação total de um time no campeonato é igual ao somatório da sua pontuação em cada janela do campeonato.

Por exemplo, se um time jogou 5 partidas em um campeonato com janelas de 3 jogos, tendo marcado 1, 3, 2, 1, 4 gols, sua pontuação total será igual a (min{1,3,2}+max{1,3,2})+(min{3,2,1}+max{3,2,1})+(min{2,1,4}+max{2,1,4}) = (1+3)+(1+3)+(1+4) = 13 pontos.

Depois de criar o modelo do novo sistema de pontuação, a CBF percebeu que não era uma tarefa muito fácil calcular a pontuação dos times para campeonatos com muitas partidas e com janelas de muitos jogos, e resolveu contratá-lo para desenvolver um programa que baseado no número de gols marcados por cada equipe, determine o campeão do campeonato e sua pontuação.

Entrada

A primeira linha da entrada contém um inteiro T, o número de casos de teste (1 ≤ T ≤ 20). Cada caso de teste é composto por várias linhas.

Na primeira linha de cada caso de teste são dados três inteiros E (1 ≤ E ≤ 20), P (1 ≤ P ≤ 106) e J (1 ≤ J ≤ P), representando, respectivamente, o número de equipes no campeonato, o número total de partidas de cada equipe e o número de partidas de cada janela. As E linhas seguintes descrevem as informações do campeonato, uma para cada equipe. Cada uma dessas linhas contém o nome da equipe (string de até 20 caracteres, contendo apenas letras minúsculas ou maiúsculas) seguido de P inteiros g1, g2, ..., gp (0 ≤ gi ≤ 1000) separados por espaços em branco, indicando os gols marcados pela equipe em cada partida do campeonato.

Saída

Para cada caso de teste, imprima uma linha contendo o nome e a pontuação total da equipe campeã do torneio, separados por um espaço em branco. Se duas ou mais equipes terminarem empatadas na liderança do campeonato com a mesma pontuação, é considerada campeã aquela que aparece primeiro na ordenação lexicográfica dos nomes.

Exemplos

Entrada:
2
2 5 3
Atletico 1 3 2 1 4
Cruzeiro 1 0 1 2 4
2 9 3
Cruzeiro 1 2 3 4 5 6 7 8 9
Atletico 9 4 2 6 7 5 3 8 1

Saída:
Atletico 13
Atletico 70

No primeiro caso de teste, a pontuação do Atletico foi igual a (1+1+1)+(3+3+4) = 13 e a do Cruzeiro foi igual a (0+0+1)+(1+2+4) = 8.

No segundo caso de teste, a pontuação do Atletico e do Cruzeiro foram iguais, mas pelo critério de desempate (ordenação lexicográfica dos nomes) o Atletico foi considerado o campeão.


Adicionado por:Wanderley Guimarăes
Data:2012-03-14
Tempo limite:2.164s
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:Seletiva UFMG 2011

hide comments
2013-08-19 13:50:48 Jozias Rolim [IFPB - João Pessoa]
É possível passar em Pyhton 2.7? Até agora ninguém conseguiu^^
2012-08-28 19:39:04 Namaste
alguem tem o arquivo com resposta pra me passar ?

Last edit: 2012-08-28 19:44:39
2012-07-17 02:40:14 Eduardo [UTFPR]
Alguém tem o arquivo in/out desse exercício?
2012-03-21 17:57:05 Fernando Fonseca [ITA]
Gostei da verossimilhança dos casos de exemplo!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.