#include <iostream>
#include <algorithm>
#include <vector>
#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;
vector<piii> pos;
bool used[3000001];
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++){
for(j=0;j<beg[i];j++)
pos.pb({a[i][j], {i, j}});
for(j=endi[i]+1;j<m;j++)
pos.pb({a[i][j], {i, j}});
}
sort(pos.begin(), pos.end());
for(i=0;i<kk;i++){
int k1=0, k2=n*kk-1;
for(j=0;j<n;j++)
usedc[j]=false;
for(j=0;j<n/2;j++){
while(true){
if(!used[k1] && !usedc[pos[k1].second.first]){
ans[pos[k1].second.first][pos[k1].second.second]=i;
used[k1]=true, usedc[pos[k1].second.first]=true;
break;
}
k1++;
}
while(true){
if(!used[k2] && !usedc[pos[k2].second.first]){
ans[pos[k2].second.first][pos[k2].second.second]=i;
used[k2]=true, usedc[pos[k2].second.first]=true;
break;
}
k2--;
}
}
}
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);
//}
