Ефективне виробництво

Є n працівників та n робот, причому i-ий працівник виконує j-ту роботу за якусь відому суму грошей. Складіть таку схему виробництва, при якій кожен працівник виконує лише одну роботу і загальна вартість виконаних робіт мінімальна.

Вхідні дані

Містить декілька тестів. Перший рядок кожного тесту містить єдине натуральне число n (2 ≤ n < 14), яке вказує на кількість працівників та робочих місць. Кожний з наступних n рядків містить по n цілих чисел, які вказують на вартість виконання i-им працівником j-ої роботи на j-ому робочому місці у рядку i.

Вартість робіт не може бути від'ємною і не перевищує 200 - економіка повинна бути економною.

Вихідні дані

Для кожного значення n виведіть в окремому рядку шукану мінімальну вартість виконання робіт.

Приклади