ICPC Scoreboard

Charles is the director of a regional programming contest. He must keep the contest running smoothly, apply the rules fairly, and announce the final ranking.

Teams are ranked first by the number of problems they solve: a team that solves more problems ranks above a team that solves fewer. When two teams solve the same number of problems, the team with the smaller total penalty ranks higher. If two teams solve the same number of problems and have the same total penalty, they are tied.

A team's total penalty is the sum of the problem penalties over the problems it has solved. For a single solved problem the problem penalty is $TP + EP \times FA$, where:

• $TP$ (the time penalty) is the number of minutes from the start of the contest until the team's first correct submission for that problem;
• $EP$ (the error penalty) is a positive integer chosen by the director, meant to reward teams that solve a problem on the first attempt;
• $FA$ is the number of failed attempts the team made on that problem before its first correct submission.

The standard error penalty is $EP = 20$. Charles wants to change it and, to study the effect on the ranking, he needs the range of error penalties that leave the final standings unchanged.

Formally, the original standings are the ones obtained with $EP = 20$. An error penalty is acceptable if, for every pair of teams A and B: whenever A ranks above B in the original standings, A still ranks above B; and whenever A and B are tied in the original standings, they are still tied. Given the teams' results, compute the range of acceptable error penalties.

The input contains several test cases. The first line of a test case has two integers $T$ and $P$ ($2 \le T \le 100$, $1 \le P \le 10$): the number of teams and the number of problems. Each of the next $T$ lines describes one team and contains $P$ problem results separated by single spaces. Teams are not necessarily listed in ranking order.

Each problem result is a string A/S. $A$ is the number of attempts the team made on that problem ($0 \le A \le 100$); attempts made after the first correct submission are not counted. $S$ is either -, meaning the team did not solve the problem, or an integer ($1 \le S \le 300$) giving the number of minutes the team took to submit a correct solution.

The line 0 0 (that is, $T = P = 0$) marks the end of the input and is not processed.

For each test case, print two values separated by a single space: the smallest and the largest error penalty (both positive integers) that leave the final standings unchanged. If there is no upper bound on the error penalty, print * in place of the largest value.