eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

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

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

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

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #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 
Вихідні дані #1
23
4 3 1 2 5