cho.shTime limit
5s
Memory limit
128 MB
There are N students and N problems. Each student must be assigned exactly one problem, and each problem must be assigned to exactly one student.
The time needed to solve a problem can be different for each student. In the table below, student 1 needs 1 hour to solve problem 1, while student 2 needs 2 hours to solve problem 1.
| Problem 1 | Problem 2 | Problem 3 | |
|---|---|---|---|
| Student 1 | 1 | 3 | 3 |
| Student 2 | 2 | 3 | 3 |
| Student 3 | 3 | 2 | 4 |
We want to minimize the total time spent by all students after assigning distinct problems to them. In the table above, assigning problem 1 to student 1, problem 3 to student 2, and problem 2 to student 3 gives a total time of 1 + 3 + 2 = 6, and no assignment has a smaller total.
Given the time each student needs for each problem, find the minimum possible total time when every student is assigned one distinct problem.
The first line contains an integer N. (1 <= N <= 100)
The next N lines contain the times in order. The j-th integer on the i-th of these lines is the time needed for student i to solve problem j.
Every given integer is at most 1,000.
Print the minimum possible total time when each student is assigned one distinct problem.