Задачи
Матрица (Easy)
Матрица (Easy)
Вам дана матрица целых чисел размера \textbf{n}×\textbf{n}. Ваша задача - найти такой набор координат (\textbf{k_i}, \textbf{l_i}), в котором каждая координата \textbf{k_i} и каждая координата \textbf{l_i} встречается ровно один раз, такой, чтобы минимизировать сумму выбранных элементов.
\InputFile
Первая строка входного файла содержит одно целое число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50}). Следующие \textbf{n} строк содержат по \textbf{n }целых чисел в каждой. Все эти числа не превосходят по абсолютной величине \textbf{10^6}.
\OutputFile
Первая строка должна содержать значение оптимизируемой функции. В следующие \textbf{n} строк необходимо записать пары чисел, описывающих выбранные ячейки. Первой координатой выводится номер строки.
Входные данные #1
2 1 1 1 1
Выходные данные #1
2 1 1 2 2