Description

A university’s required course “Software Engineering” is divided into a theory part and a practice part. The theory part is taught by professors at the university. The practice part is led by a third-party company: students need to learn HTML, css, JavaScript, vue, Python, django, and other technologies by themselves within five weeks, and form teams to complete a real internet business application.

There are $n(0\le n \le 1000)$ students taking this course. They are divided into no more than $26$ teams, and each team is represented by a letter from A to Z. Each team completes a project and, as a team, gives scores to all teams (including their own team). The scores are integers from $0$ to $100$.

To calm students’ dissatisfaction caused by many issues of this course (such as too much workload, overly tight schedule, unfair assessment method, etc.), the teacher decides to use a method that “looks” fair to determine each team’s project score:

For a given team, first compute the average of all scores given to this team by all teams (including itself). Then remove the scores that differ from this average by more than $15$ points (it is guaranteed that not all scores will be removed). Finally, compute the average of the remaining scores, round it to the nearest integer, and use it as the team’s project score.

For each student, we already know their team code and theory score (also an integer from $0$ to $100$). The student’s final score is $60\%$ of the theory score plus $40\%$ of the project score of their team, then rounded to the nearest integer.

Now the teacher wants to know the ranking of all students’ scores. Please output each student’s score and their team, in descending order of final score.

Input Format

The first line contains two integers $n$ and $k$, representing the number of students and the number of teams.

The next $n$ lines each contain an integer $s_i$ and an uppercase letter $c_i$, representing the theory score of the $i$-th student and their team ID. It is guaranteed that the team IDs are among the consecutive $k$ letters starting from A.

The next $k$ lines each contain $k$ integers. The integer $a_{i,j}$ in row $i$ and column $j$ represents the score given by team $i$ to team $j$. When $i=j$, it is the self-score.

Output Format

Output $n$ lines as the answer. Students with higher scores should be output first. If scores are the same, students with a smaller team ID should be output first. For each line, first output the student’s score, then output the uppercase letter representing their team ID.

6 3
70 A
80 A
65 B
95 B
85 C
90 C
70 90 100
95 88 85
30 47 100

93 B
92 C
89 C
76 A
75 B
70 A

Hint

The scores received by team A are $70,95,30$. Their average is $65$, so $95,30$ are removed as invalid scores. Therefore, team A’s project score is $70$.
The scores received by team B are $90,88,47$. Their average is $75$, so $47$ is removed as an invalid score. Therefore, team B’s project score is $89$.
The scores received by team C are $100,85,100$. Their average is $95$, so no score is removed. Therefore, team C’s project score is $95$.

Translated by ChatGPT 5