Matrix

You are given an n×n matrix of integers. Your task is to identify a set of coordinates (k_i, l_i) such that each row index k_i and each column index l_i is used exactly once. The goal is to minimize the sum of the elements at these selected coordinates.

Input

The input begins with a single integer n (1 ≤ n ≤ 239). The next n lines each contain n integers. Each integer in the matrix is within the range of -10^6 to 10^6.

Output

The output should start with a single line containing the minimized sum. Following this, output n lines, each containing a pair of numbers representing the selected cell coordinates, with the row number listed first.

Examples