Top Three Students

Given a set of students with their exam scores and a list of weights corresponding to each exam, compute each student's weighted average score using the formula:

\(\text{Score} = \sum_{i=1}^{m} s_i \times w_i\)

Output the names of the top three students ranked by their weighted average scores in descending order. In case of a tie in scores, the student names should be sorted in ascending lexicographical order. If there are fewer than three students, output all of them.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer N, the number of students.
• The second line contains an integer M, the number of exams.
• The third line contains M floating-point numbers representing the weights for each exam.
• Then follow N lines, each containing a student's name (a string without spaces) followed by M integers representing that student's exam scores.

outputFormat

Output a single line to stdout containing the names of the top three students (or all students if there are less than three), separated by a space, sorted by their weighted average scores in descending order. In the event of tied scores, sort those students lexicographically in ascending order.

4
3
0.3 0.4 0.3
Alice 90 80 70
Bob 85 95 80
Charlie 100 70 90
David 70 75 85

Bob Charlie Alice