Problem D
#exclude<scoring>
You are participating in a programming contest cup. The cup consists of a series of programming contests, followed by a final at the end of the season for the $15$ top ranked contestants in the cup. With only one contest left to go before the final, you are starting to wonder if your performance in the earlier contests has been good enough to already secure you a spot in the finals. If so, you could succumb to your laziness and skip the last contest.
The ranking of the cup works as follows. In each contest, a contestant earns some number of points between $0$ and $101$ (the details of this are described below). Their aggregate score is then defined to be the sum of the four highest scores achieved. For instance if a contestant got $45$, $15$, $32$, $0$, $30$, and $20$ points over $6$ contests, their aggregate score is $45+32+30+20=127$. The rank of a contestant X in the cup is defined to be $1$ plus the number of contestants that have a strictly larger aggregate score than X.
The score a contestant earns from a contest is based on the rank they achieve in that contest, according to the following table.
|
Rank |
Points |
Rank |
Points |
Rank |
Points |
|
$1$ |
$100$ |
$11$ |
$24$ |
$21$ |
$10$ |
|
$2$ |
$75$ |
$12$ |
$22$ |
$22$ |
$9$ |
|
$3$ |
$60$ |
$13$ |
$20$ |
$23$ |
$8$ |
|
$4$ |
$50$ |
$14$ |
$18$ |
$24$ |
$7$ |
|
$5$ |
$45$ |
$15$ |
$16$ |
$25$ |
$6$ |
|
$6$ |
$40$ |
$16$ |
$15$ |
$26$ |
$5$ |
|
$7$ |
$36$ |
$17$ |
$14$ |
$27$ |
$4$ |
|
$8$ |
$32$ |
$18$ |
$13$ |
$28$ |
$3$ |
|
$9$ |
$29$ |
$19$ |
$12$ |
$29$ |
$2$ |
|
$10$ |
$26$ |
$20$ |
$11$ |
$30$ |
$1$ |
If a contestant gets a worse rank than $30$, they get $0$ points. If two or more contestants get the same rank in the contest, they are instead assigned the average points of all the corresponding ranks. This average is always rounded up to the closest integer. For example, if three contestants are tied for second place they all receive $\lceil \frac{75 + 60 + 50}{3} \rceil = 62$ points, and the next contestant will have rank $5$ and receives $45$ points (or less, if there is a tie also for $5$’th place). This applies also at rank $30$, e.g., if $4\, 711$ contestants are tied for $30$’th place, they all receive $1$ point.
Contestants may participate in every contest either on-site or online. If they compete on-site, they get $1$ extra point, no matter their original number of points. If a contestant does not participate in a contest, they get $0$ points.
Input
The first line of input contains two integers $n$ and $m$ ($2 \le n \le 10$, $1 \le m \le 10^5$), where $n$ is the number of contests in the cup (excluding the final), and $m$ is the number of people who participated in any of the first $n-1$ contests.
Then follow $m$ lines, each describing a contestant. Each such line consists of $n-1$ integers $0 \le s_1, \ldots , s_{n-1} \le 101$, where $s_ i$ is the score that this contestant received in the $i$th contest.
The first contestant listed is you. The point values in the input might not correspond to actual points from a contest.
Output
Output a single integer $r$, the worst possible rank you might end up in after the last contest, assuming you do not participate in it.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 50 50 75 25 25 25 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 2 50 50 50 50 25 25 25 25 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 4 90 1 3 2 |
3 |
