#include "tickets.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
typedef long long ll;
struct paar{
ll l,r,su,hun;
};
bool boo(paar e,paar v){
if(e.su!=v.su) return e.su<v.su;
if(e.hun!=v.hun) return e.hun<v.hun;
return e.l<v.l;
}
long long find_maximum(int k, vector<vector<int> > x) {
int n = x.size();
int m = x[0].size();
vector<vector<int> > answer;
vector<paar> p;
vector<int> ees[1505],tag[1505];
bool b[1505];
ll arv;
paar pp;
for (int i = 0; i < n; i++) {
vector<int> row(m);
for (int j = 0; j < m; j++)
row[j] = -1;
answer.push_back(row);
}
ll tul=0;
for(int i=0; i<n; i++) for(int j=0; j<k; j++){
pp.l=j; pp.r=j+(m-k); pp.su=x[i][j]+x[i][j+(m-k)]; pp.hun=i;
p.push_back(pp);
}
sort(p.begin(),p.end(),boo);
for(int i=0; i<(k*n)/2; i++)
tul+=x[p[k*n-i-1].hun][p[k*n-i-1].r]-x[p[i].hun][p[i].l];
for(int i=0; i<k*n; i++) if(i<(k*n)/2)
ees[p[i].hun].push_back(p[i].l);
else tag[p[i].hun].push_back(p[i].r);
for(int i=0; i<k; i++){
arv=0;
for(int j=0; j<n; j++) b[j]=0;
for(int j=0; j<n; j++) if(tag[j].size()==0) arv++,answer[j][ees[j][ees[j].size()-1]]=i,ees[j].pop_back(),b[j]=1;
for(int j=0; j<n; j++) if(arv<(n/2) && !b[j] && ees[j].size()) arv++,answer[j][ees[j][ees[j].size()-1]]=i,ees[j].pop_back(),b[j]=1;
for(int j=0; j<n; j++) if(!b[j]) answer[j][tag[j][tag[j].size()-1]]=i,tag[j].pop_back(),b[j]=1;
}
allocate_tickets(answer);
return tul;
}
