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

Однією з класичних задач комбінаторної оптимізації є так звана "задача про призначення". Формулюється вона наступним чином.

Є $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)$.

Вихідні дані

Виведіть мінімальну можливу вартість призначення.

Приклади