Task Assignment

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},\ldots,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 \le n \le 200$

$1 \le c_{ij} \le 1000$

Example

Input

4
17 8 16 9
7 15 12 19
6 9 10 11
14 7 13 10

Output

33
1 4
2 1
3 3
4 2

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.