시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB21150.000%

문제

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 ⌈(75+60+50)/3⌉ = 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.

입력

The first line of input contains two integers n and m (2 ≤ n ≤ 10, 1 ≤ m ≤ 105), 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 ≤ s1, . . . , sn−1 ≤ 101, where si is the score that this contestant received in the ith contest.

The first contestant listed is you. The point values in the input might not correspond to actual points from a contest.

출력

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.

예제 입력 1

4 2
50 50 75
25 25 25

예제 출력 1

2

예제 입력 2

5 2
50 50 50 50
25 25 25 25

예제 출력 2

1

예제 입력 3

2 4
90
1
3
2

예제 출력 3

3

출처

Contest > KTH Challenge > KTH Challenge 2018 D번

  • 문제를 만든 사람: Per Austrin