Задача о назначениях

Дана квадратная матрица из натуральных чисел порядка n. Выберите n элементов из этой матрицы, так, чтобы:

1. в каждой строке и в каждом столбце находился ровно 1 выбранный элемент;

2. из всех наборов, удовлетворяющих первому условию, сумма выбранных чисел должна быть наименьшей.

Если таких наборов несколько — выведите любой.

Входные данные

В первой строке записано натуральное число n (1 ≤ n ≤ 200). В каждой из следующих n строк записано по nчисел. Каждый элемент матрицы не превосходит 1000.

Выходные данные

В первую строку выведите сумму найденных чисел. Во вторую строку выведите n чисел. i-ое число в последовательности должно обозначать такой номер столбца, что на пересечении i-ой строки и данного столбца стоит выбранный элемент. Очевидно, эта последовательность должна быть перестановкой чисел от 1 до n.

Примеры