Problem Description

A historic competition is about to begin, organized by ACM. Specifically, there are $n$ teams competing for the top spot, including the Croatian golden trio: Paula, Marin, and Josip. The competition follows the standard format, where team members collaborate to write and submit code.

The contest consists of $m$ different problems, and teams are ranked by the number of problems they have solved (non-increasing order). Teams with the same number of solved problems are ranked by a so-called penalty time (non-decreasing order). The penalty time for a team is the sum of the penalties they received for each correctly solved problem. The penalty for a correctly solved problem is the time taken by the team to solve it (from the start of the competition) plus an additional penalty.

Each failed submission adds 20 minutes to the team's penalty time. No team will submit code for a problem they have already solved, and each team can submit a maximum of 9 times for each problem. If teams have the same number of solved problems and the same penalty time, they are ranked lexicographically in the leaderboard.

The competition lasts 5 hours. For the first 4 hours, all teams can see the rankings and the status of each problem for every team (number of submissions, whether it is solved, and when it was solved). During these 4 hours, the rankings are automatically updated after each submission. However, in the last hour, the leaderboard is frozen, meaning that after evaluating new submissions, the rankings of the teams do not update. During this time, each team knows the results of their own submissions but not those of other teams. They only know which tasks other teams have submitted, how many times, and the last submission time for each task.

The competition has ended, and the leaderboard will soon be unfrozen. Our heroes, NijeZivotJedanACM, need your help. They want to know their worst possible rank on the leaderboard after it is unfrozen. Please help them!

Input Format

The input data consists of $1 + n$ lines.

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

The next $n$ lines describe the status of each team:
1. The team name is first.
2. Following this, $m$ strings in the format SX/V are provided, where:
- S indicates the problem status with three possible characters: - (not solved), + (solved), ? (last submission when the leaderboard was frozen).
- X is the number of submissions for that problem. If no submissions were made, X is omitted.
- V is the time of the last submission in HH:MM:SS format, possibly with leading zeros. If the problem was not solved, the /V part is omitted.

The last line follows the same format and describes NijeZivotJedanACM's final status (after the leaderboard is unfrozen).

Output Format

The output consists of one line.

The line should output the worst possible rank NijeZivotJedanACM could have after the leaderboard is unfrozen.

Sample Input and Output

Input Sample #1

2 1
NijeZivotJedanACM -
ZivotJESTJedanACM -
NijeZivotJedanACM -

Output Sample #1

1

Input Sample #2

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 -

Output Sample #2

2

Input Sample #3

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

Output Sample #3

3

Notes/Hints

Data Size and Constraints

• For 40% of the data, all S states are guaranteed not to be ?.
• For 100% of the data, $1 \le n \le 1000$, $1 \le m \le 15$, and all team names are unique in the test data.

Notes

This problem is worth 50 points.

Translated from COCI2019-2020 CONTEST #2 T1 ACM.

见题面 Input 部分

见题面 Output 部分