Task about Appointment

Given a square matrix of natural numbers with order n, your task is to select n elements from this matrix such that:

1. There is exactly 1 selected element in each row and each column.

2. Among all sets that satisfy the first condition, the sum of the selected numbers is minimized.

If multiple sets satisfy these conditions, you may output any one of them.

Input

The first line contains a natural number n (1 ≤ n ≤ 200). Each of the following n lines contains n numbers. Each element of the matrix is at most 1000.

Output

On the first line, output the sum of the selected numbers. On the second line, output n numbers. The i-th number in this sequence should indicate the column number where the selected element is located at the intersection of the i-th row and the specified column. This sequence should be a permutation of numbers from 1 to n.

Examples