Server Time: Sat Sep 22, 2018 3:06 am
 Welcome ( logout )
 PDF (English) Statistics Forum
 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 pij denotes the profit if we put the ith gift into the jth box. Now your task is to pack all the gifts and maximize the profit.

# Input

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].

# Output

For each case, print the case number and the maximum profit.

# 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

Problem Setter: Jane Alam Jan
 Developed and Maintained by JANE ALAM JAN Copyright © 2012 LightOJ, Jane Alam Jan