#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<pii, int> piii;
int n, m, kk;
vector<vector<int> > a;
int beg[1501], endi[1501];
vector<piii> subt;
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]], ans[i][endi[i]]=j, endi[i]--;
subt.pb({{a[i][endi[i]]+a[i][beg[kk-j-1]], i}, j});
}
}
sort(subt.begin(), subt.end());
for(i=0;i<n*kk/2;i++){
piii f=subt[j];
ansval-=f.first.first;
ans[f.first.second][endi[f.first.second]]=-1, endi[f.first.second]++;
ans[f.first.second][beg[f.first.second]]=f.second, beg[f.first.second]++;
}
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}});
//}
