50149. Admission

I'm a slow walker, but I never walk backwards.

Task Description

We want to determine the $M$ students to enter our university according to their grades in the entrance examination. The examination contains five subjects: Chinese, English, Math, Science, and Social Study. We will admit students according to the following rules. We first compare the total scores from all five subjects, and admit the top $M$ students with highest total scores. If there are ties in the total scores, we will compare (in this order) their scores of Math, English, Science, Chinese, and finally Social Study.

There could be extra-admission. That is, if the $M$-{th} student has the same scores on $all$ subjects as the $(M+1)$-{th} student, then we will admit all these students (with the same scores on all subjects) until we find the next student that has a lower priority. Please refer to the following example. The sorted student ID list (in decreasing priority) will be 0, 2, 1, 3, 4. Now if $M$ is $3$, we will admit students 0, 2, 1, and 3 since students 1 and 3 have the same scores in all subjects. We will not admit student 4 since he has a lower score than student 3, and the extra-admission stops.

Input Format

The first line has two numbers $M$ and $N$. $M$ is the number of students to admit and $N$ is the total number of students. The following $N$ lines are scores of students. There are six numbers in each line: student ID and five scores of each subject in the order of Chinese, English, Math, Science, and Social Study.

  • $0 \lt M \leq N \leq 20000$
  • $0 \leq \text{score} \leq 100$

Output Format

The output lists the admitted students’ ID by ranking. If there are students with the same scores on all subjects, then output the student with smaller ID first.

Subtasks

  • 10 points: $M$ is $1$, and there is no extra-admission.
  • 40 points: $M$ is more than $1$, and there is no extra-admission.
  • 50 points: $M$ is more than $1$, and there could be extra-admission.

Sample Input 1

1 3
0 100 100 100 100 70
1 100 100 100 100 100
2 70 100 100 100 100

Sample Output 1

1

Sample Input 2

3 5
0 100 100 100 100 70
1 100 100 100 100 100
2 70 100 100 100 100
3 100 100 100 100 0
4 0 0 0 0 0

Sample Output 2

1
0
2

Sample Input 3

3 5
0 100 100 100 100 100
1 100 100 100 100 80
2 100 100 100 100 100
3 100 100 100 100 80
4 100 100 80 100 100

Sample Output 3

0
2
1
3

Discussion