Имеется n рабочих и n работ, причём i-ый рабочий выполняет j-ую работу за какую-то известную сумму денег. Составьте такую схему производства, при которой каждый рабочий выполняет только одну работу и общая стоимость выполненных работ минимальна.

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

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

Стоимость работ не может быть отрицательной и не превышает 200 - экономика должна быть экономной.

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

Для каждого теста выведите в отдельной строке искомую минимальную стоимость выполнения всех работ.