smoothie-web Problems Contests Ranking About
Login Register

BSSPC 2019 P9 - Timetables

data_usage Points
timer Time Limit
linear_scale Memory Limit

Problem Statement

The school has been finishing up making the timetables for students next year, but now have to determine the placings of students who did not get the courses they want. For each student, they hate some courses more than others, so we can assign a hate value for each student per course. Help the school by making a program to assign students to courses while minimizing the total hate value from all of the students.

Note: Only one student can be assigned to one course spot, and each student only gets one course spot.

Input Specification

The first line will contain the integer NN (1N251 \le N \le 25), which is the number of students that still need a course, and the number of course spots available.

The following N lines each contain integers (d1,d2,...,dNd_1, d_2 , ..., d_N) with did_i (0di<2000000 \le d_i < 200000) being the hate value the student has for course spot ii.

For 3 out the 10 marks available, N3N \le 3.

Output Specification

Output one integer, which is the minimum total hate value that the students collectively have with an optimal course placing.

Sample Input

1 2 3
5 4 3
10000 5 10

Sample Output



For the first course spot, it is best to let student 1 to have the course spot, since her hate value is 1, which is lower than all of the other students spot. For course spot 2, while it’s best to give the spot to student 3, since student 3’s hate value for course spot 3 is much higher than student 2’s. After assigning the students to their course spot, we can add up the hate values, to get 9: