#include "tickets.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto dfh:v)cout<<dfh<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=1505;
ll a[MAXN][MAXN];
vector<vector<int>> us; // i,j used in round us[i][j]
ll n,m,k;
ll c[MAXN][2];
set<ll>pos[MAXN];
void useij(ll i, ll j, ll idx){
us[i][j]=idx;
pos[i].erase(j);
c[i][a[i][j]]--;
}
/*void use(ll i, ll x, ll idx){ //from row i use element = to x in oper idx
fore(j,0,m){
if(us[i][j]==-1&&a[i][j]==x){
us[i][j]=idx;
pos[i].erase(j);
return;
}
}
assert(0);
}*/
/*void use_all(ll x, ll idx){ //if can use x in every row
vector<ll>op;
fore(i,0,n){
for(auto j:pos){
if(!c[i][x]){
op.pb(j);
break;
}
else {
if(a[i][j]==x){
op.pb(j);
break;
}
}
}
}
fore(i,0,SZ(op))useij(i,op[i],idx);
}*/
long long find_maximum(int K, std::vector<std::vector<int>> A){
k=K;
n=SZ(A);
m=SZ(A[0]);
fore(i,0,n)fore(j,0,m)a[i][j]=A[i][j];
us.resize(n,vector<int>(m,-1));
if(m==1){
//sub m=1
vector<ll>b;
fore(i,0,n)b.pb(a[i][0]),us[i][0]=0;
sort(ALL(b));
ll sum=0;
fore(i,0,n)sum+=abs(b[i]-b[n/2]);
allocate_tickets(us);
return sum;
}
//ll is_sub=1;
//fore(i,0,n)fore(j,0,m)if(a[i][j]>1)is_sub=0;
fore(i,0,n)fore(j,0,m)c[i][a[i][j]]++;
fore(i,0,n)fore(j,0,m)pos[i].insert(j);
ll res=0;
fore(idx,0,k){
vector<ll>q(2);
fore(i,0,n){
if(!c[i][0])q[1]++;
if(!c[i][1])q[0]++;
}
vector<ll>u(2);
if(q[0]>=n/2)u[0]=0,u[1]=n-q[0]-q[1];
else if(q[1]>=n/2)u[1]=0,u[0]=n-q[0]-q[1];
else u[0]=n/2-q[0],u[1]=n/2-q[1];
res+=min(q[0]+u[0],q[1]+u[1]);
fore(i,0,n){
if(!c[i][0])useij(i,*pos[i].begin(),idx);
else if(!c[i][1])useij(i,*pos[i].begin(),idx);
else {
for(auto j:pos[i])if(u[a[i][j]]){
useij(i,j,idx),u[a[i][j]]--;
break;
}
}
}
}
allocate_tickets(us);
return res;
}
