Efficient production

There are n people and n job to do. The i-th person can do the j-th job for a certain amount of money. Find a scheme where every person does only one different job, and total cost to do all jobs is minimum.

Input

Contains several test cases. The first line of each case is the number of persons (and jobs) n (2 ≤ n < 14). Each of the next n lines contains n integers, the cost for i-th person to do the j-th job equals to the j-th element in line i.

Cost of the work can not be negative and usually less than 200 - the economy must be economical.

Output

For each test case print in one line the minimum cost to do all jobs.

Examples