Computing Worst Final Rank for NijeZivotJedanACM

During an ICPC contest with a modified rule set, there are m problems and n teams. Each team has a unique name. The ranking is determined by the following criteria:

• The team that solves more problems ranks higher.
• If teams solve the same number of problems, the one with a lower total penalty time ranks higher.
• If both the number of problems solved and the penalty time are identical, then the team whose name is smaller in lexicographical order ranks higher.

For each solved problem, the penalty time is calculated as the time of the last correct submission plus an extra 20 minutes for every wrong submission made prior to the correct one. (Note that once a team solves a problem, they do not submit any further solutions for that problem.)

In the contest, the first 4 hours the scoreboard is live and updates with each submission. In the last hour the scoreboard is frozen (although submission data is still being recorded, teams only see whether their own submissions are correct). When the contest ends, the scoreboard is unfrozen, revealing all teams' results.

Your task is to help the team NijeZivotJedanACM determine the worst possible final ranking they could have given the following input data. For every team other than NijeZivotJedanACM, it is assumed that during the frozen period they achieved all their pending ("potential") solves optimally — i.e. they solved as many additional problems as possible (not exceeding the total number of problems) without incurring any extra penalty time. Note that the target team, NijeZivotJedanACM, does not improve its result further during the frozen period.

Formally, suppose a team has currently solved s problems with a penalty of p and has a potential of r additional solves in the frozen period. Then after unfreezing, the team’s results are updated as follows:

\(\text{new\_solved} = s + \min(r, m - s)\)

The penalty time remains p. The ranking is then determined by comparing teams with the following ordered criteria:

1. Higher number of solved problems.
2. Lower penalty time.
3. Lexicographically smaller team name.

Your program must compute the worst ranking for team NijeZivotJedanACM (i.e. 1 plus the number of teams that can potentially rank above it).

Note: All formulas are presented in \(\LaTeX\) format (when applicable) and any divergence from the official rules is to be disregarded in favor of the description above.

inputFormat

The first line of input contains two integers n and m (1 ≤ n, m ≤ 1000), representing the number of teams and the number of problems, respectively.

Each of the following n lines describes a team with four tokens separated by spaces:

• team_name — a string (without spaces). Note that team names are unique.
• s — an integer, the number of problems solved in the visible period.
• p — an integer, the total penalty time accumulated so far.
• r — an integer, the number of problems that can potentially be solved during the frozen period.

It is guaranteed that the team named NijeZivotJedanACM will appear exactly once in the input. For teams other than NijeZivotJedanACM, assume that during the unfreeze, they will convert as many of their potential pending submissions into accepted solutions as possible, but they cannot solve more than the total number of problems m (i.e. for a team with current solves s and potential r, the final number of solves is \( s + \min(r, m-s) \)). Their penalty time does not change.

outputFormat

Output a single integer representing the worst possible final ranking (1-indexed) of team NijeZivotJedanACM.

sample

3 5
NijeZivotJedanACM 2 150 0
TeamB 2 140 1
TeamA 1 100 2

3