Matrix (Easy)

You are given an ( n $\times$ 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, in order to minimize the sum of the selected matrix elements.

Input

The first line of the input contains a single integer ( n ) ((1 $\le$ n $\le$ 50)). The following ( n ) lines each contain ( n ) integers. Each of these integers is within the range of (-10^6) to (10^6).

Output

The first line of the output should display the minimized sum. In the subsequent ( n ) lines, list the pairs of numbers representing the selected cells, with the row number given first.

Examples