1416 - Placar do ICPC

ID: 1416
IdBecrowd: 1416
Tags: geometria, programacao-dinamica, strings
Nível: 9
Tempo Limite: 3 segundos
Memória: 200 MB
Categoria: Paradigmas
Autor: Fabio Dias Moreira, PUC-Rio, Brasil.

Descrição

Charles é o diretor de torneio do torneio regional do ICPC de Tumbolia. Sua responsabilidade é garantir que o torneio corra perfeitamente, 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 + EP x FA, onde TP é a penalidade de tempo para aquele problema, EP é a penalidade de erro do competidor 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 performance 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 penalidade por erro que não alteraria a colocação final. Se não existir um limite superior para a penalidade por erro, imprima um “*” ao invés do limite superior.

Exemplos

Exemplo de 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

Exemplo de Saída