#include "tickets.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=2e3+50;
const ll mod=1e9+7;
using namespace std;
int n,m,i,j,nr,vz[nmax],t,l[nmax],f[nmax];
vector<vector<int> >rs;
vector<pair<int,pair<int,int> > >vc;
vector<int>v[2][nmax];
vector<pair<int,int> >ea,eb,fft;
set<pair<int,int> >s,b;
set<pair<int,int> >::iterator it;
ll sm;
ll find_maximum(int k,vector<vector<int> > a)
{
n=lun(a),m=lun(a[0]);
/*for(i=0;i<n;i++)for(j=0;j<m;j++)vc.pb(mkp(a[i][j],mkp(i,j)));
sort(all(vc));
for(i=0;i<n*m;i++)
{
v[i<n*m/2][vc[i].sc.fr].pb(vc[i].sc.sc);
if(i<n*m/2)sm-=1LL*vc[i].fr;
else sm+=1LL*vc[i].fr;
}
for(i=0;i<n;i++)
{
if(!v[0][i].empty())b.in(mkp(lun(v[0][i]),i));
if(!v[1][i].empty())s.in(mkp(lun(v[1][i]),i));
}*/
rs.resize(n);
for(i=0;i<n;i++)for(j=0;j<m;j++)rs[i].pb(-1);
for(i=0;i<n;i++)l[i]=m-1;
for(i=0;i<k;i++)
{
fft.clear();
for(j=0;j<n;j++)
{
fft.pb(mkp(a[j][l[j]],j));
}
sort(all(fft));
for(j=0;j<n/2;j++)
{
t=fft[j].sc;
rs[t][f[t]]=i;
sm-=1LL*a[t][f[t]];
f[t]++;
}
for(;j<n;j++)
{
t=fft[j].sc;
rs[t][l[t]]=i;
sm+=1LL*a[t][l[t]];
l[t]--;
}
/*for(j=0;j<n;j++)vz[j]=0;
nr=0;
ea.clear(),eb.clear();
it=--s.end();
for(j=0;j<n/2;j++)
{
t=it->sc;
rs[t][v[1][t].back()]=i;
v[1][t].pop_back();
vz[t]=1;
ea.pb(*it);
it--;
}
it=--b.end();
for(j=0;j<n/2;j++)
{
while(vz[it->sc])it--;
t=it->sc;
rs[t][v[0][t].back()]=i;
v[0][t].pop_back();
vz[t]=1;
eb.pb(*it);
it--;
}
for(j=0;j<lun(ea);j++)
{
s.er(s.fd(ea[j]));
if(ea[j].fr>1)s.in(mkp(ea[j].fr-1,ea[j].sc));
}
for(j=0;j<lun(eb);j++)
{
b.er(b.fd(eb[j]));
if(eb[j].fr>1)b.in(mkp(eb[j].fr-1,eb[j].sc));
}*/
}
allocate_tickets(rs);
return sm;
}
/*int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
return 0;
}*/
