#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; #define LL __int64 using namespace std; double mp[20][2000], d[200], cost; const int INF=0x3f3f3f3f; int head[200], source, sink, cnt, flow; int f[200], cur[200], vis[200]; struct node { int u, v, cap, next; double cost; } edge[100000]; void add(int u, int v, int cap, double cost) { edge[cnt].v=v; edge[cnt].cap=cap; edge[cnt].cost=cost; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].cap=0; edge[cnt].cost=-cost; edge[cnt].next=head[v]; head[v]=cnt++; } int spfa() { int i; for(i=0; i<200; i++) d[i]=INF; memset(vis,0,sizeof(vis)); cur[source]=-1; f[source]=INF; d[source]=0; queue<int>q; q.push(source); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(d[v]>d[u]+edge[i].cost&&edge[i].cap) { d[v]=d[u]+edge[i].cost; f[v]=min(f[u],edge[i].cap); cur[v]=i; if(!vis[v]) { vis[v]=1; q.push(v); } } } } if(d[sink]==INF) return 0; flow+=f[sink]; cost-=f[sink]*d[sink]; for(i=cur[sink]; i!=-1; i=cur[edge[i^1].v]) { edge[i].cap-=f[sink]; edge[i^1].cap+=f[sink]; } return 1; } void mcmf() { cost=flow=0; while(spfa()) ; } int main() { int t, num=0, i, j, k, n, m; double sum; scanf("%d",&t); while(t--) { sum=0; num++; scanf("%d%d",&n,&m); for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { scanf("%lf",&mp[i][j]); } } k=1; sum=0; while(k<=m) { source=0; sink=2*n+1; memset(head,-1,sizeof(head)); cnt=0; for(i=k; i<k+n&&i<=m; i++) { add(i-k+1+n,sink,1,0); for(j=1; j<=n; j++) { add(j,i-k+1+n,1,-mp[j][i]); } } for(i=1; i<=n; i++) add(source,i,1,0); mcmf(); sum+=cost; //printf("%.2lf %d ",sum, k); k+=n; } printf("Case #%d: %.5lf ",num,sum); } return 0; }