SPOJ Brasil

Charles é o diretor de torneio do torneio regional do ICPC de Tumbolia. Sua responsabilidade é garantir que o torneio corra perfeitamento, que as regras sejam seguidas, e, claro, anunciar o placar final da competição.

De acordo com as regras do ICPC, um time com mais problemas resolvidos fica acima de um time com menos problemas resolvidos. Se dois times têm o mesmo número de problemas resolvidos, o time com a menor penalidade fica acima (no caso de os dois times terem o mesmo número de problemas resolvidos e a mesma penalidade, Charles considera eles empatados).

A penalidade total de um time é a soma da penalidade de todos problemas que o time resolveu. A penalidade de um problema é TP+EPxFA, onde TP é a penalidade de tempo para aquele problema, EP é a penalidade de erro da competição e FA é o número de tentativas frustradas de resolver o problema antes de submeter uma solução certa.

A penalidade de tempo para um problema é o tempo desde o início da competição, em minutos, que time demorou para resolver o problema. A penalidade de erro é um inteiro positivo escolhido pelo diretor do torneio, designada para premiar times que submetam soluções corretas na primeira tentativa.

Charles quer mudar a penalidade de erro do valor “padrão” de 20 minutos para esquentar as coisas. Para estudar os efeitos dessa mudança no placar final, ele quer saber o limite de penalidades de erro que não mudam as posições finais.

Em outras palavras, se o time A está na frente do time B no placar original, então A deve estar na frente de B no placar modificado; se A e B estão empatados no placar original, eles devem estar empatados no placar modificado (o placar original é aquele obtido com uma penalidade de erro de 20 minutos).

Charles está muito ocupado organizando a regional tumboliana, então ele pediu para você fazer um programa que vai calcular o limite para ele.

Entrada

A entrada contém diversos casos de teste. A primeira linha de cada caso de teste contém dois inteiros T e P separados por um espaço, indicando o número de times e o número de problemas, respectivamente (2 <= T <= 100, 1 <= P <= 10). Cada uma das próximas T linhas descreve a perfomance de um time. A descrição da performance de um time é uma linha contendo P descrições de problemas separados por um espaço em branco. Os times não são necessariamente dados na ordem da colocação final.

A descrição de cada problema é uma string “A/S”, onde A é um inteiro representando o número de tentativas que o time correspondente fez para resolver o problema (0 <= A <= 100), e S pode ser tanto “-”, se o time não resolveu o problema, ou um inteiro indicando quantos minutos o time demorou para submeter um solução correta (1 <= S <= 300). Tentativas feitas depois da primeira correta não são contadas.

O final da entrada é dado por T = P = 0.

Saída

Para cada caso de teste da entrada imprima dois inteiros positivos separados por um espaço, indicando a menor e a maior penalidades por erro que não alterariam a colocação final. Se não existir um limite superior para a penalidade por erro, imprima um “*” ao invés do limite superior.

Exemplo

Entrada
5 3
0/- 0/- 0/-
2/- 2/- 1/-
1/60 1/165 1/-
1/80 0/- 2/120
0/- 1/17 0/-
4 2
17/- 5/-
2/7 3/-
3/- 2/-
1/15 0/-
3 2
1/- 2/15
2/53 1/17
1/70 1/20
0 0

Saída
1 24
9 *
20 20