Задача про призначення

Задано квадратну матрицю з натуральних чисел порядку n. Виберіть n елементів з цієї матриці, так, щоб:

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

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

Якщо таких наборів декілька — виведіть довільний.

Вхідні дані

У першому рядку записано натуральне число n (1 ≤ n ≤ 200). У кожному з наступних n рядків записано по n чисел. Кожен елемент матриці не перевищує 1000.

Вихідні дані

У перший рядок виведіть суму знайдениых чисел. У другий рядок виведіть n чисел. i-те число у послідовності повинно позначати такий номер стовбця, що на перетині i-го рядка і заданого стовбця стоїть вибраний елемент. Очевидно, ця послідовність повинна бути перестановкою чисел від 1 до n.

Приклади