#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int nn,mm;
int a[1501][1501];
pair<int,int> b[1501][1501];
long long ans2;
int z;
bool in;
struct help
{
int x,y,i;
help() {}
help(int _x,int _y,int _i)
{
x=_x;
y=_y;
i=_i;
}
bool operator<(const help&h)const
{
return abs(abs(h.y-z)-abs(h.x-z))>abs(abs(x-z)-abs(y-z));
}
};
int g[16];
void rec(int j)
{
if(j==nn)
{
vector<int> h;
for(int i=0; i<nn; i++)
h.push_back(a[i][g[i]]);
sort(h.begin(),h.end());
long long sz=h.size()/2,ans=0;
for(int i=0; i<nn; i++)
ans+=abs(h[i]-h[sz]);
if(ans>ans2)
{
cout<<"!"<<" "<<ans<<endl;
for(int i=0; i<nn; i++)
cout<<g[i]<<" ";
cout<<endl;
in=1;
}
//cout<<ans<<endl;
return;
}
for(int i=0; i<mm; i++)
{
g[j]=i;
rec(j+1);
}
}
vector<vector<int> > v;
int id[200001],maxx[200001],minn[200001];
pair<int,int> cnt[200001];
long long try_(int x,int p)
{
//cout<<x<<" !"<<endl;
z=x;
priority_queue<help> q;
if(a[p][minn[p]]==x)id[p]=1;
else id[p]=2;
long long ans=0;
int l=0,m=0;
for(int i=0; i<nn; i++)
{
if(i==p)continue;
if(a[i][maxx[i]]<x)
{
ans+=x-a[i][minn[i]];
id[i]=1;
l++;
}
else if(a[i][minn[i]]>x)
{
ans+=a[i][maxx[i]]-x;
id[i]=2;
m++;
}
else
{
//cout<<"here"<<" "<<i<<endl;
q.push({a[i][minn[i]],a[i][maxx[i]],i});
}
}
int l1=nn/2;
if(nn%2==0)l1--;
int l2=nn/2;
if(l>l1)return -1;
if(m>l2)return -1;
//cout<<"pos"<<endl;
while(q.size())
{
help h=q.top();
q.pop();
if(h.y-z>z-h.x&&m<l2||l==l1)
{
m++;
id[h.i]=2;
ans+=h.y-z;
}
else
{
l++;
id[h.i]=1;
ans+=z-h.x;
}
}
return ans;
}
int t[1501];
int l[1501],r[1501];
long long find_maximum(int k, std::vector<std::vector<int>> x)
{
v=x;
nn=x.size();
mm=x[0].size();
for(int i=0; i<nn; i++)
{
for(int j=0; j<mm; j++)
{
v[i][j]=-1;
a[i][j]=x[i][j];
}
}
if(mm==1)
{
vector<int> h;
for(int i=0; i<nn; i++)
h.push_back(a[i][0]);
sort(h.begin(),h.end());
long long sz=h.size()/2,ans=0;
for(int i=0; i<nn; i++)
ans+=abs(h[i]-h[sz]);
for(int i=0; i<nn; i++)
v[i][0]=0;
allocate_tickets(v);
return ans;
}
for(int i=0; i<nn; i++)
{
minn[i]=maxx[i]=0;
for(int j=1; j<mm; j++)
{
if(a[i][maxx[i]]<a[i][j])
maxx[i]=j;
if(a[i][minn[i]]>a[i][j])
minn[i]=j;
}
if(minn[i]==maxx[i])
{
minn[i]=1;
}
}
if(k==1)
{
long long ans=-1;
for(int i=0; i<nn; i++)
{
long long t1=try_(a[i][maxx[i]],i);
if(ans<t1)
{
ans=t1;
for(int j=0; j<nn; j++)
if(id[j]==1)v[j][minn[j]]=0,v[j][maxx[j]]=-1;
else v[j][minn[j]]=-1,v[j][maxx[j]]=0;
}
long long t2=try_(a[i][minn[i]],i);
if(ans<t2)
{
ans=t2;
for(int j=0; j<nn; j++)
if(id[j]==1)v[j][minn[j]]=0,v[j][maxx[j]]=-1;
else v[j][minn[j]]=-1,v[j][maxx[j]]=0;
}
}
ans2=ans;
//rec(0);
allocate_tickets(v);
return ans;
}
for(int i=0;i<nn;i++)
{
r[i]=mm-1;
int c=0;
for(int j=0;j<mm;j++)
c+=a[i][j];
cnt[i]={c,i};
}
int ans=0;
for(int i=0;i<k;i++)
{
sort(cnt,cnt+nn);
//for(int j=0;j<nn;j++)
// cout<<cnt[j].first<<" - "<<cnt[j].second<<" "<<l[cnt[j].second]<<" "<<r[cnt[j].second]<<endl;
int h=0;
for(int id=0;id<nn/2;id++)
{
int j=cnt[id].second;
if(a[j][l[j]])h++,cnt[id].first--;
v[j][l[j]++]=i;
j=cnt[nn-id-1].second;
if(a[j][r[j]])h++,cnt[nn-id-1].first--;
v[j][r[j]--]=i;
}
ans+=min(h,nn-h);
}
allocate_tickets(v);
return ans;
}
/*int main()
{
while(1)
{
int n,m,k;
n=rand()%10+1;
m=rand()%3+1;
k=1;
vector<vector<int> > f;
for(int i=0;i<n;i++)
{
f.push_back({});
for(int j=0;j<m;j++)
f[i].push_back(rand()%10+1);
}
cout<<find_maximum(k,f)<<endl;
if(in)
{
cout<<n<<" "<<m<<" "<<k<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cout<<f[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
}
}
*/
