Description

A contest with a long history is about to begin, organized by ACM. More precisely, there are $n$ teams competing for first place, including the Croatian golden trio: Paula, Marin, and Josip. The contest uses the standard format: team members work together, write code, and submit it.

The contest consists of $m$ different problems. Teams are ranked by the number of solved problems (non-increasing).

Teams with the same number of solved problems are ranked by the so-called penalty time (non-decreasing). A team’s penalty time is the sum of the penalty times they got for each correctly solved problem. The penalty time for a correctly solved problem equals the time the team spent to solve that problem (from the start of the contest), plus additional penalty minutes.

Each submitted but rejected solution adds $20$ minutes of penalty to the team that submitted it. No team will submit for a problem they have already solved, and for each team, the maximum number of submissions per problem is $9$. If some teams have the same number of solved problems and the same penalty time, they are ordered lexicographically on the scoreboard.

The contest lasts $5$ hours. During the first $4$ hours, all teams can see the scoreboard, including information about each team’s status on each problem (number of submissions, whether it has been solved, and when it was solved). During these $4$ hours, the scoreboard is automatically updated after every submission. However, in the last $1$ hour, the scoreboard is frozen: after judging new submissions, the rankings do not change. During this time, each team knows the judging results of their own submissions, but does not know the judging results of other teams’ submissions. They only know which problems other teams submitted, how many times they submitted, and the time of the last submission for each problem.

The contest has ended, and the scoreboard will soon be unfrozen. Our heroes, NijeZivotJedanACM, need your help. They want to know the worst possible rank they could end up with after the scoreboard is unfrozen. Please help them!

Input Format

The input has $n + 2$ lines.

The first line contains two integers $n$ and $m$, representing the number of teams and the number of problems.

The next $n$ lines describe the teams, each in the following format:

1. First, the team name.
2. Then $m$ strings, each in the form SX/V, described as follows:

• S is the problem status and is one of three characters: -, +, ?. - means the team did not solve this problem, + means the team solved this problem, and ? means the scoreboard was frozen at the time of the last submission for this problem.
• X is the number of submissions the team made for this problem. In particular, if the team made no submissions for this problem, then X is omitted.
• V is the time since the contest started at the moment of the team’s last submission for this problem, written as HH:MM:SS and may contain leading zeros. In particular, if the problem is not solved, then the entire /V part is omitted.

The last line, in the same format as above, gives the final result of NijeZivotJedanACM (i.e., the result after the scoreboard is unfrozen).

Output Format

The output has one line.

Print the worst possible rank that NijeZivotJedanACM may have.

2 1
NijeZivotJedanACM -
ZivotJESTJedanACM -
NijeZivotJedanACM -

1

3 2
StoJeZivot ?1/04:00:00 +1/02:04:06
JeLiZivotJedanACM ?1/04:59:59 -
NijeZivotJedanACM ?1/04:42:43 -
NijeZivotJedanACM +1/04:42:43 -

2

7 4
NisamSadaNistaDonio +1/03:59:59 +3/03:42:02 +2/00:14:59 ?1/04:56:12
JeLiMojKockaSeUmio ?4/04:00:00 -3 +1/00:10:01 +9/03:04:42
OstaviDobroJe ?4/04:59:59 -1 +2/00:24:15 +8/03:24:45
DobroJeOstavi +1/01:42:53 - ?9/04:58:23 ?1/04:34:43
NijeZivotJedanACM ?2/04:50:05 ?4/04:32:12 +2/01:32:45 ?1/04:59:59
KoSeToSeta ?1/04:23:32 - +9/01:00:00 -9
SipSipSipSipSipSip - - - ?9/04:00:00
NijeZivotJedanACM -2 +4/04:32:12 +2/01:32:45 +1/04:59:59

3

Hint

Constraints

• For $40\%$ of the testdata, all input statuses S are guaranteed not to be ?.
• For $100\%$ of the testdata, $1 \le n \le 1000$, $1 \le m \le 15$, and in all testdata, any two teams have different names.

Notes

This problem is worth $50$ points.

Translated from COCI2019-2020 CONTEST #2 T1 ACM.

Translated by ChatGPT 5