ICPC 스코어보드

Charles는 어느 지역 프로그래밍 대회의 운영 책임자이다. 그는 대회가 원활히 진행되도록 하고, 규칙을 공정하게 적용하며, 최종 순위를 발표해야 한다.

팀의 순위는 먼저 푼 문제 수로 정해진다. 더 많은 문제를 푼 팀이 더 적게 푼 팀보다 앞선다. 푼 문제 수가 같으면 총 페널티가 더 작은 팀이 앞선다. 푼 문제 수와 총 페널티가 모두 같은 두 팀은 공동 순위(무승부)로 본다.

한 팀의 총 페널티는 그 팀이 푼 문제들의 문제 페널티를 모두 더한 값이다. 어떤 한 문제를 풀었을 때의 문제 페널티는 $TP + EP \times FA$ 이며, 각 값의 의미는 다음과 같다.

• $TP$(시간 페널티)는 대회 시작 후 그 문제의 첫 정답 제출까지 걸린 시간(분)이다.
• $EP$(오답 페널티)는 대회 운영자가 정하는 양의 정수로, 문제를 한 번에 맞힌 팀에게 유리하도록 설계된 값이다.
• $FA$는 그 문제의 첫 정답 제출 이전에 낸 오답(실패한 시도)의 개수이다.

표준 오답 페널티는 $EP = 20$이다. Charles는 이 값을 바꾸려 하는데, 순위에 미치는 영향을 알아보기 위해 최종 순위를 그대로 유지하는 오답 페널티의 범위를 알고 싶다.

정확히 말하면, 원래 순위는 $EP = 20$으로 계산한 순위이다. 어떤 오답 페널티가 "허용된다"는 것은 모든 두 팀 A, B에 대해 다음을 만족한다는 뜻이다. 원래 순위에서 A가 B보다 앞섰다면 바뀐 순위에서도 A가 B보다 앞서야 하고, 원래 순위에서 A와 B가 공동 순위였다면 바뀐 순위에서도 공동 순위여야 한다. 각 팀의 결과가 주어질 때, 허용되는 오답 페널티의 범위를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 팀 수 $T$와 문제 수 $P$가 공백으로 구분되어 주어진다 ($2 \le T \le 100$, $1 \le P \le 10$). 이어지는 $T$개의 줄은 각각 한 팀의 결과를 나타내며, $P$개의 문제 결과가 공백으로 구분되어 주어진다. 팀은 최종 순위 순으로 주어지지 않을 수도 있다.

각 문제 결과는 A/S 형식의 문자열이다. $A$는 그 팀이 해당 문제에 시도한 횟수이며 ($0 \le A \le 100$), 첫 정답 제출 이후의 시도는 세지 않는다. $S$는 -이면 그 문제를 풀지 못한 것이고, 정수이면 ($1 \le S \le 300$) 정답을 제출하기까지 걸린 시간(분)이다.

0 0(즉 $T = P = 0$)인 줄은 입력의 끝을 나타내며 처리하지 않는다.

각 테스트 케이스마다 최종 순위를 바꾸지 않는 오답 페널티의 최솟값과 최댓값(모두 양의 정수)을 공백으로 구분하여 한 줄에 출력한다. 오답 페널티의 최댓값에 상한이 없으면 최댓값 자리에 *를 출력한다.