Problems
Задача о назначениях
Задача о назначениях
Дана квадратная матрица из натуральных чисел порядка \textbf{n}. Выберите \textbf{n} элементов из этой матрицы, так, чтобы:
\begin{enumerate}
\item в каждой строке и в каждом столбце находился ровно \textbf{1} выбранный элемент;
\item из всех наборов, удовлетворяющих первому условию, сумма выбранных чисел должна быть наименьшей.
\end{enumerate}
Если таких наборов несколько --- выведите любой.
\InputFile
В первой строке записано натуральное число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{200}). В каждой из следующих \textbf{n} строк записано по \textbf{n}чисел. Каждый элемент матрицы не превосходит \textbf{1000}.
\OutputFile
В первую строку выведите сумму найденных чисел. Во вторую строку выведите \textbf{n} чисел. \textbf{i}-ое число в последовательности должно обозначать такой номер столбца, что на пересечении \textbf{i}-ой строки и данного столбца стоит выбранный элемент. Очевидно, эта последовательность должна быть перестановкой чисел от \textbf{1} до \textbf{n}.
Input example #1
5 7 10 5 3 7 10 6 6 10 9 7 7 7 5 9 5 1 4 7 7 5 10 6 5 6
Output example #1
23 4 3 1 2 5