영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
A company has n employees and there are n tasks that need to be done. We know for each employee the cost of carrying out each task. Every employee should be assigned to exactly one task. What is the minimum total cost if we assign the tasks optimally and how could they be assigned?
Input
The first input line has one integer n: the number of employees and the number of tasks that need to be done.
After this, there are n lines each consisting of n integers. The ith line consists of integers c_i1,c_i2,…,c_in: the cost of each task when it is assigned to the ith employee.
Output
First print the minimum total cost.
Then print n lines each consisting of two integers a and b: you assign the bth task to the ath employee.
If there are multiple solutions you can print any of them.
Constraints
- 1 ≤ n ≤ 200
- 1 ≤ c_ij ≤ 1000
Example
Explanation: The minimum total cost is 33. We can reach this by assigning employee 1 task 4, employee 2 task 1, employee 3 task 3 and employee 4 task 2. This will cost 9 + 7 + 10 + 7 = 33.
예제
예제 1
4 17 8 16 9 7 15 12 19 6 9 10 11 14 7 13 10
33 1 4 2 1 3 3 4 2