#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include "tickets.h"
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
int n, m, kk;
vector<vector<int> > a;
int beg[1501], endi[1501];
vector<pii> subt;
set<pii> co, co2;
vector<pii> insback;
set<pii>:: iterator it, it2;
bool usedc[1501];
ll ansval=0;
vector<int> plamt;
vector<vector<int> > ans;
ll find_maximum(int kkk, vector<vector<int> > x)
{
int i, j;
n=x.size(), m=x[1].size(), kk=kkk;
a=x;
for(i=0;i<m;i++)
plamt.pb(-1);
for(i=0;i<n;i++)
ans.pb(plamt);
for(i=0;i<n;i++)
endi[i]=m-1;
for(i=0;i<n;i++){
for(j=0;j<kk;j++){
ansval+=a[i][endi[i]];
subt.pb({a[i][endi[i]]+a[i][kk-j-1], i});
endi[i]--;
}
}
sort(subt.begin(), subt.end());
for(i=0;i<n*kk/2;i++){
pii f=subt[i];
ansval-=f.first;
beg[f.second]++, endi[f.second]++;
}
for(i=0;i<n;i++){
co.insert({beg[i], i});
co2.insert({m-endi[i], i});
}
for(i=0;i<kk;i++){
for(j=0;j<n;j++)
usedc[j]=false;
insback.clear();
for(j=0;j<n/2;j++){
it=co.end(), it--;
pii f=*it;
co.erase(it);
f.first--;
ans[f.second][f.first]=i, usedc[f.second]=true;
insback.pb(f);
}
for(j=0;j<n/2;j++)
co.insert(insback[j]);
insback.clear();
j=0;
it=co2.end(), it--;
while(j<n/2){
if(!usedc[it->second]){
it2=it, it2--;
pii f=*it;
co2.erase(it);
f.first--;
ans[f.second][m-f.first]=i, usedc[f.second]=true;
insback.pb(f);
it=it2, j++;
}
else
it--;
}
for(j=0;j<n/2;j++)
co2.insert(insback[j]);
}
allocate_tickets(ans);
return ansval;
}
//int main()
//{
// int i, j;
//
// cin >> n >> m >> kk;
// for(i=0;i<m;i++)
// plamt.pb(0);
// for(i=0;i<n;i++)
// a.pb(plamt);
// plamt.clear();
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++){
// int x;
// cin >> x;
// a[i-1][j-1]=x;
// }
// find_maximum(kk, a);
//
// return 0;
//}
