Untitled

#include <bits/stdc++.h>
#define MAXN 1005
using namespace std;

int love[200][1000];
int ex_jub[200];
int ex_seeker[1000];
int vis_jub[200];
int vis_seeker[1000];
int match[1000],matchInv[200];
int n,m,minz;

bool dfs(int job){
    vis_jub[job]=true;

    for(int seeker=0;seeker<n;seeker++){
        if(!vis_seeker[seeker] && ex_jub[job]+ex_seeker[seeker]==love[job][seeker]){
            vis_seeker[seeker]=true;
            if(match[seeker]==-1 || dfs(match[seeker])){
                match[seeker]=job;
                matchInv[job]=seeker;
                return true;
            }
        }else if(!vis_seeker[seeker]){
            minz=min(minz,ex_jub[job]+ex_seeker[seeker]-love[job][seeker]);
        }
    }
    return false;
}

void init(){
    for(int i=0;i<n;i++){
        ex_seeker[i]=0;
        match[i]=-1;
    }
    for(int i=0;i<m;i++){
        ex_jub[i]=love[i][0];
        matchInv[i]=-1;
        for(int j=1;j<n;j++){
            ex_jub[i]=max(ex_jub[i],love[i][j]);
        }
    }
}

void update(){
    for(int i=0;i<m;i++){
        if(vis_jub[i]) ex_jub[i]-=minz;
    }
    for(int i=0;i<n;i++){
        if(vis_seeker[i]) ex_seeker[i]+=minz;
    }
}

int KM(){
    init();

    //KM
    for(int i=0;i<m;i++){  //為每個jub都配對一個seeker
        while(1){
            //init
            memset(vis_jub,0,sizeof(ex_jub));
            memset(vis_seeker,0,sizeof(ex_seeker));
            minz=1e9;

            if(!dfs(i)) update();  //如果配對失敗,則更新頂標
            else break;  //直到配對成功
        }
    }
    
    int ans=0;
    for(int i=0;i<m;i++){
        ans+=love[i][matchInv[i]];
    }
    return ans;
}

int main(){
    cin.sync_with_stdio(0),cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin >> love[j][i];
            }
        }
        cout << KM() << '\n';
    }
    return 0;
}