eolymp
bolt
Try our new interface for solving problems
Problems

Efficient production

Efficient production

Time limit 10 seconds
Memory limit 123 MiB

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 data

Contains several test cases. The first line of each case is the number of persons (and jobs) n (2n < 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 data

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

Examples

Input example #1
3
10 93 73
12 69 40
88 62 76
Output example #1
112