DoctorNiGONiGO has developed a new kind of multi-core CPU, it works as follow. Thereare q (1 < q ≤ 50) identical cores in the CPU, and there are p (0 < p ≤ 200) jobs need to be done. Each job should run in some core andneed only one unit time. The cores in the CPU can work simultaneously but eachcore can implement only one job at a time. When a job completed, it will incura deferral cost. Job i has a deferralcost c(i, j) (0 ≤ c(i, j) ≤ 1000000), where j is the completion time of the job (1 ≤j ≤ p because any job done in the time later than p obviously not the optimal solution). Here we assume that c(i, j)is a monotonically no decreasing function of j. Now you are asked to find the schedule which have the minimumoverall deferral cost.<o:p></o:p>
DoctorNiGONiGO’smulti-coreCPU
Input
An integer T indicated the number of test cases.
For each test case:
There are two integers q, p in first line.
And Following is p lines, each line contain p integer, the jth integer of the ith line is the deferral cost c(i, j).
For each test case:
There are two integers q, p in first line.
And Following is p lines, each line contain p integer, the jth integer of the ith line is the deferral cost c(i, j).
Output
For each test case, output a singer integer, which is the minimum total deferral cost of the Problem.
Sample Input
1
2 4
89 145 181 269
4 86 158 164
60 143 157 165
4 45 109 207
Sample Output
</p>254
HINT
a. In the sample case, core 1 execute the job 2, 1 in sequence; core 2 execute the job 3, 4 in sequence, thus the optimal solution has the overall cost (4 + 145) + (60 + 45) = 254.
b. Huge input.