#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 cnt=0, cnt2=0;
for(j=0;j<n;j++)
usedc[j]=false;
j=0;
while(cnt<n/2){
if(!used[j] && !usedc[pos[j].second.first]){
ans[pos[j].second.first][pos[j].second.second]=i;
cnt++, used[j]++, usedc[pos[j].second.first]=true;
}
j++;
}
j=n*kk-1;
while(cnt2<n/2){
if(!used[j] && !usedc[pos[j].second.first]){
ans[pos[j].second.first][pos[j].second.second]=i;
cnt2++, used[j]++, usedc[pos[j].second.first]=true;
}
j--;
}
}
allocate_tickets(ans);
return ansval;
}
//int main()
//{
// find_maximum(2, {{0, 2, 5},{1, 1, 3}});
// find_maximum(1, {{5, 9}, {1, 4}, {3, 6}, {2, 7}});
// find_maximum(3, {{0, 1, 1, 1, 1, 1}, {0, 0, 0, 1, 1, 1}, {0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1}});
//}
