Time Limit: 1 second(s) | Memory Limit: 32 MB |
There are n gifts and n boxes, each box can contain at most one gift. Now you want to pack all the gifts in the boxes such that your profit is as high possible.
The boxes are numbered from 1 to n and the gifts are numbered from 1 to n. You will be given an (n x n) matrix where p_{ij} denotes the profit if we put the i^{th} gift into the j^{th} box. Now your task is to pack all the gifts and maximize the profit.
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 50). Each of the next n lines contains n space separated integers forming the matrix. The values in the matrix lie in the range [0, 1000].
For each case, print the case number and the maximum profit.
Sample Input |
Output for Sample Input |
2 2 4 3 3 1 3 1 4 5 5 7 6 5 8 8 |
Case 1: 6 Case 2: 18 |
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |