#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[1509][1509],k,pi,ee,qi,tes,t;
long long jm;
pair <int, int> q[3000009];
pair <int, pair <int, int> > p[3000009];
int bo[1509];
vector <vector <int> > ans;
/*void allocate_tickets(vector <vector <int> > XX){
int qw=0,we=0;
for(qw=0; qw<a; qw++){
for(we=0; we<b; we++){
cout<<XX[qw][we]<<" ";
}
cout<<endl;
}
}*/
long long find_maximum(int K, vector<vector<int> > Xx) {
k=K;
a=Xx.size();b=Xx[0].size();
ans.resize(a);
for(i=0; i<a; i++){
ans[i].resize(b);
for(j=0; j<b; j++){
f[i][j]=Xx[i][j];
}
}
jm=0;
for(i=0; i<a; i++){
for(j=0; j<k; j++){
jm-=f[i][j];
bo[i]++;
ii=i;jj=b-(k-j);
pi++;
p[pi].first=-(f[i][jj]+f[i][j]);
p[pi].second=make_pair(i,jj);
}
}
sort(p+1,p+pi+1);
for(i=1; i<=pi; i++){
p[i].first=-p[i].first;
}
ee=a*k/2;
for(e=1; e<=ee; e++){
i=p[e].second.first;j=p[e].second.second;
jm+=p[e].first;
ii=i;jj=b-(k-j);
bo[i]--;
}
for(i=0; i<a; i++){
for(j=0; j<b; j++){
ans[i][j]=-1;
}
}
t=0;
while(k>0){
qi=-1;
for(i=0; i<a; i++){
qi++;
q[qi].first=bo[i];
q[qi].second=i;
}
sort(q,q+qi+1);
for(ii=0; ii<a/2; ii++){
i=q[ii].second;
j=b-(k-bo[i]);
ans[i][j]=t;
}
for(ii=a/2; ii<a; ii++){
i=q[ii].second;
j=bo[i]-1;
ans[i][j]=t;
bo[i]--;
}
k--;t++;
}
allocate_tickets(ans);
return jm;
}
/*int main(){
vector <vector <int> > qw;
cin>>a>>b>>k;
qw.resize(a);
for(i=0; i<a; i++){
for(j=0; j<b; j++){
cin>>c;
qw[i].push_back(c);
}
}
cout<<find_maximum(k,qw);
return 0;
}*/
