Programming Contest Cup

Time limit1sMemory limit512 MB

Summary

Given every contestant's scores from the first n-1 contests, find the worst rank you can end up at if you skip the last contest and others play it optimally against you.

Level: Medium6 of 10
Topics: Greedy, Sorting, Simulation
Solved: No attempts yet

Problem

You are taking part 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. Only one contest is left before the final. You want to know whether your results so far have already secured a spot in the final. If they have, you may skip the last contest.

The cup ranking works as follows. In each contest, a contestant earns between 0 and 101 points. The aggregate score is the sum of the four highest scores the contestant achieved. For example, if a contestant got 45, 15, 32, 0, 30, and 20 points over 6 contests, the aggregate score is 45 + 32 + 30 + 20 = 127. The rank of a contestant X is 1 plus the number of contestants whose aggregate score is strictly larger than X's.

Points in a contest depend on the rank achieved, according to the table below. A rank worse than 30 earns 0 points.

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 contestants share a rank, each of them receives the average points of the tied ranks, rounded up to the nearest integer. For example, if three contestants tie for second place, each receives $\lceil (75+60+50)/3 \rceil = 62$ points, and the next contestant has rank 5 and receives 45 points (or fewer, if 5th place is also tied). The same rule applies at rank 30. If 4711 contestants tie for 30th place, each of them receives 1 point.

A contestant may take part in each contest either on-site or online. An on-site participant gets 1 extra point, regardless of the original points. A contestant who does not take part in a contest gets 0 points.

Input

The first line 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 took part in at least one of the first $n-1$ contests.

The next $m$ lines each describe one contestant with $n-1$ integers $0 \le s_1, \ldots, s_{n-1} \le 101$ , where $s_i$ is the score that contestant received in the $i$ -th contest. The first contestant listed is you.

The point values in the input may not match actual contest points.

Output

Print a single integer $r$ , the worst possible rank you might end up in after the last contest, assuming you do not take part in it.

Examples3

Example 1
Input
```
4 2
50 50 75
25 25 25
```
Expected output
```
2
```
Example 2
Input
```
5 2
50 50 50 50
25 25 25 25
```
Expected output
```
1
```
Example 3
Input
```
2 4
90
1
3
2
```
Expected output
```
3
```

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

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

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