Old MacDonald had a farm, iyaiyayo. But after so many years, some rocks and weeds grow in the farm and cost it much to clean them up. The farm can be seen as an rectangle which can be divided into n*m square areas. Old MacDonald needs to clean up at least k square areas. Since Old MacDonald is very old, he hope that after cleaned up, for any two cleaned area A and B, one can go from A to B using at most 1 turn and any square on the path must be cleaned.
Unfortunately, cleaning a square on (i, j) cost Old MacDonald c_ij dollars. Please find the minimum cost for him.
First line contains an integer T (T<=100) indicating the number of test cases. For each test case, first line contains three integers n, m, k (1<=n, m<=15, 0<=k<=n*m) denoting the size of the farm. Each of the next n lines contains m integers. The j-th number of the i-th line c_ij (0<=c_ij<=10000) denotes the cost on (i, j).
Even if the cost is zero, you still need to clean it.
For each test case, please output the minimum cost.
1 3 3 4 10 10 10 1 2 3 4 10 10
10
Migrated from old NTUJ.
tmt514
| No. | Testdata Range | Score |
|---|