Problem
You need to do n different jobs. In this case, you have a list of n handymen and prices, for how many dollars which worker does what work.
Distribute workers so that you spend less money in total. At the same time, you want to do everything in one day, so the workers will work in parallel. Thus, each worker will perform exactly one task.
Input:
In the first line you are given a positive number n (1 <= n <= 8) - the number of jobs and workers.
The next n lines contain n positive integers separated by spaces - matrix A, where A
i,j shows how many dollars the worker number i will do work number j. For all A
i,j 1 <= A
i,j <= 10
5.
Output:
Print a single number - the minimum cost for which you can hire these workers for all available jobs.
Example:
| Input |
Output |
3
3 1 2
5 6 4
7 8 9
| 12 |
Explanation:
The first worker will do the second job, the second worker the third job, and the third worker the first job. The total cost is 1 + 4 + 7 = 12.