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

Одной из классических задач комбинаторной оптимизации является так называемая "задача о назначениях". Формулируется она следующим образом.

Есть $n$ работников, пронумерованных числами от $1$ до $n$, и $n$ работ, также пронумерованных числами от $1$ до $n$. Если $i$-ый работник выполняет $j$-ую работу, то ему выплачивается зарплата в размере $c_{ij}$ денежных единиц. Необходимо найти такое назначение работников на работы (каждый работник выполняет ровно одну работу, каждая работа выполняется ровно одним работником), что суммарная зарплата работников минимальна (соответствующая сумма называется стоимостью назначения).

Напишите программу, решающую задачу о назначениях.

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

Первая строка содержит целое число $n(1\le n\le 10)$.

Каждая из следующих $n$ строк содержит $n$ чисел. При этом $j$-ое число $(i+1)$-ой строки равно $c_{ij}(1\le c_{ij}\le 1000)$.

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

Выведите минимальную возможную стоимость назначения.

Примеры