An ancient programming competition is getting near and it is organized by none other
than ACM (Aeronautic Centre of Metković). Exactly ~N~ teams will compete for the
grand prize and among them is a golden Croatian trio: Paula, Marin and Josip. The
contest format is standard, while the pilot is performing aerobatic maneuvers, the
co-pilot reads the problem statements and attempts to transmit the solutions to the
code monkey main programmer who is securely taped to the aircraft's exterior.
The contest consists of ~M~ different tasks and the teams are (non-increasingly) ordered
by the number of solved tasks.
The contest consists of ~M~ different tasks and the teams are (non-increasingly) ordered by the number of solved tasks.
The teams that have the same number of solved tasks are ordered (non-decreasingly) by so-called penalty time. Penalty time of a certain team is the sum of penalty time they achieved on each of their correctly solved tasks. Penalty time of a correctly solved task equals to the time it took for the team to solve that task (from the beginning of the contest) increased by additional 20 minutes for each of the wrongly submitted solutions for that task. No teams will attempt to submit a solution for a problem that they have already solved and the maximum number of submissions for a certain task is 9 for each team. If some teams have the same number of solved problems and the same penalty time, they will be ordered alphabetically in the final standings.
The competition lasts for five hours. During the first four hours the standings are available to all teams and contain information about the status of each task for each team (number of submissions, whether it was solved and when). During those four hours, the order of the teams will be automatically updated after each submission. In the last hour though, the standings become frozen, i.e., the order of the teams is not updated after a new submission is judged. During that time, each team knows the judgement of their own submissions, but they don't know the judgement of submissions made by other teams. They only know which tasks were submitted by other teams, how many times were they submitted and when was the last submission for each task.
The contest is over and the standings should be unfrozen soon. Our heroes, team named
need your help. They want to know what is the worst possible position on the scoreboard they could end
up in after the standings become unfrozen. Help them!
The first line contains integers ~N~ ~(1 \le N \le 1000)~ and ~M~ ~(1 \le M \le 15)~ from the task description.
The next ~N~ lines represent the frozen standings. Each line begins by a team name (string made up of lowercase and uppercase English letters which consists of at most ~20~ characters, names of all teams will be different) which is separated by a space from ~M~ (also space-separated) strings that hold the information about the status of each task for that team.
Those strings are of the form
Srepresents the status of the task –
+means the task is solved correctly,
-means it is solved incorrectly and
?means that the last submission was sent when the standings were already frozen.
Xrepresents the number of submissions that were sent by that team for this specific task. It is omitted if no submissions were made for that task.
Vrepresents the time when the last submission was sent by that team for this specific task. It is given in the format
HH:MM:SS(with leading zeroes) and is less than ~5~ hours. The whole
/Vpart is omitted if the task is not solved correctly (status
The last line contains the unfrozen standings of our heroes, team named
In the first and only line you should output the worst possible position in the standings where our heroes might end up in after the standings become unfrozen.
In test cases worth a total of ~20~ points, the input won't contain the
Sample Input 1
2 1 NijeZivotJedanACM - ZivotJESTJedanACM - NijeZivotJedanACM -
Sample Output 1
Explanation For Sample 1
Nothing will change after the standings our unfrozen. Therefore, our heroes will remain in the first place!
Sample Input 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 -
Sample Output 2
Explanation For Sample 2
In the worst case our heroes will only lose from the team
StoJeZivot, thereby finishing in second place.
Sample Input 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
Sample Output 3
Explanation For Sample 3
In the worst case our heroes will lose from teams
JeLiMojKockaSeUmio, thereby finishing in third place.