The Windy‘s is a world famous toy factory that owns M top-class workshop to make toys. This year the manager receives N orders for toys. The manager knows that every order will take different amount of hours in different workshops. More precisely, the i-th order will take Z_ij hours if the toys are making in the j-th workshop. Moreover, each order‘s work must be wholly completed in the same workshop. And a workshop can not switch to another order until it has finished the previous one. The switch does not cost any time.

The manager wants to minimize the average of the finishing time of the N orders. Can you help him?

The first line of input is the number of test case. The first line of each test case contains two integers, N and M (1 ≤ N,M ≤ 50).
The next N lines each contain M integers, describing the matrix Z_ij (1 ≤ Z_ij ≤ 100,000) There is a blank line before each test case.

For each test case output the answer on a single line. The result should be rounded to six decimal places.

#include <stdio.h>#include <iostream>#include <algorithm>#include <cstdlib>#include <sstream>#include <numeric>#include <cstring>#include <bitset>#include <string>#include <deque>#include <stack>#include <cmath>#include <queue>#include <set>#include <map>using namespace std;#define INF 0x3f3f3f3f#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)#define CLR(arr,val) memset(arr,val,sizeof(arr))#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);typedef pair<int, int> pii;typedef long long LL;const double PI = acos(-1.0);const int N = 55;const int MAXV = N + N * N;const int MAXE = N + N * N + N * N * N;struct edge{    int to, nxt, cap, cost;    edge() {}    edge(int _to, int _nxt, int _cap, int _cost): to(_to), nxt(_nxt), cap(_cap), cost(_cost) {}};edge E[MAXE << 1];int head[MAXV], tot;int vis[MAXV], pre[MAXV], path[MAXV], d[MAXV];int Z[N][N];int mc, mf;void init(){    CLR(head, -1);    tot = 0;    mc = mf = 0;}inline void add(int s, int t, int cap, int cost){    E[tot] = edge(t, head[s], cap, cost);    head[s] = tot++;    E[tot] = edge(s, head[t], 0, -cost);    head[t] = tot++;}int spfa(int s, int t){    queue<int>Q;    Q.push(s);    CLR(d, INF);    CLR(vis, 0);    d[s] = 0;    vis[s] = 1;    while (!Q.empty())    {        int u = Q.front();        Q.pop();        vis[u] = 0;        for (int i = head[u]; ~i; i = E[i].nxt)        {            int v = E[i].to;            if (d[v] > d[u] + E[i].cost && E[i].cap > 0)            {                d[v] = d[u] + E[i].cost;                pre[v] = u;                path[v] = i;                if (!vis[v])                {                    vis[v] = 1;                    Q.push(v);                }            }        }    }    return d[t] != INF;}void MCMF(int s, int t){    int i;    while (spfa(s, t))    {        int Min = INF;        for (i = t; i != s; i = pre[i])            Min = min(Min, E[path[i]].cap);        for (i = t; i != s; i = pre[i])        {            E[path[i]].cap -= Min;            E[path[i] ^ 1].cap += Min;        }        mf += Min;        mc += Min * d[t];    }}int main(void){    int tcase, n, m, i, j, k;    scanf("%d", &tcase);    while (tcase--)    {        init();        scanf("%d%d", &n, &m);        for (i = 1; i <= n; ++i)            for (j = 1; j <= m; ++j)                scanf("%d", &Z[i][j]);        int S = 0, T = n + n * m + 1;        for (i = 1; i <= n; ++i) //n源点到需加工物品            add(S, i, 1, 0);        for (i = n + 1; i <= n + n * m; ++i) //n*m加工时间点到汇点            add(i, T, 1, 0);        for (i = 1; i <= n; ++i)        {            for (j = 1; j <= m; ++j)            {                for (k = 1; k <= n; ++k)//遍历不同时间点                {                    int id = j * n + k;                    add(i, id, 1, k * Z[i][j]); //n*m*n                }            }        }        MCMF(S, T);        printf("%.6f\n", mc * 1.0 / n);    }    return 0;}