Модуль: Перебор перестановок


Задача

2 /4


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

Задача

Вам необходимо выполнить n различных работ. При этом у вас есть список из n разнорабочих и цены, за сколько долларов какой рабочий какую работу выполняет.
Распределите рабочих так, чтобы потратить суммарно меньше денег. При этом вы хотите сделать все дела за один день, поэтому рабочие будут работать параллельно. Таким образом, каждый рабочий будет выполнять ровно одно задание.

Входные данные
В первой строке вам дано положительное число n (1 <= n <= 8) - количество работ и рабочих.
В следующих n строках дано по n положительных чисел, разделенных пробелами - матрица А, где Ai,j показывает за сколько долларов рабочий под номером i выполнит работу под номером j. Для всех Ai,j выполнено 1 <= Ai,j <= 105.

Выходные данные
Выведите одно число - минимальную стоимость, за которую вы можете нанять данных рабочих на все имющиеся дела.


Пояснение к примеру
Первый рабочий выполнит вторую работу, второй рабочий третью работу и третий рабочий первую работу. Итоговая стоимость 1 + 4 + 7 = 12.


Примеры
Входные данныеВыходные данные
1 3
3 1 2
5 6 4
7 8 9
12

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6410
Java1
Python76
Комментарий учителя