SPOJ Brasil

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 p₁, p₂, ..., p_P, que são agrupadas em janelas sobrepostas de J partidas. A i-ésima janela é formada pelas partidas {p_i, p_i+1, ..., p_i+J-1}. Assim, a primeira janela do campeonato corresponde às partidas {p₁, p₂, ..., p_J}, a segunda janela corresponde às partidas {p₂, p₃, ..., p_J+1}, e assim por diante, totalizando P-J+1 janelas no campeonato.

Sejam g₁, g₂, ..., g_J os gols marcados por uma equipe em uma determinada janela do campeonato. A pontuação da equipe nessa janela é dada por min{g₁, g₂, ..., g_J} + max{g₁, g₂, ..., g_J}, 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 ≤ 10⁶) 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 g₁, g₂, ..., g_p (0 ≤ g_i ≤ 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.