#include "tickets.h"
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
#include <queue>
using namespace std;
struct A
{
int where;
int con1,con2;
}tt[1505];
priority_queue < pair < pair < long long ,int > , pair < int , int > > , vector < pair < pair < long long ,int > , pair < int , int > > > , less < pair < pair < long long ,int > , pair < int , int > > > > xx,yy;
vector < vector < int > > answer;
vector < int > row;
vector< vector<int> > all;
vector < pair < int , pair < int , int > > > how;
vector < int > uu2[1505];
set < int > uu[1505];
bool have[1505][1505];
bool have2[305][90005];
bool use[1505]={0};
long long DP[1505][1505];
long long DP2[305][90005];
long long con[1505][1505];
int a[1505];
int b[1505];
int N,M;
long long find_maximum(int k,vector< vector<int> > x)
{
long long ans=0;
int i,j,ll,rr;
pair < pair < long long ,int > , pair < int , int > > aa,bb;
N=x.size();
M=x[0].size();
for(i=0;i<N/2;i++)
{
for(j=0;j<k;j++)
{
ans-=x[i][j];
uu[i].insert(j);
}
xx.push(make_pair(make_pair(x[i][k-1]+x[i][M-1],i),make_pair(k-1,M-1)));
}
for(i=N/2;i<N;i++)
{
for(j=0;j<k;j++)
{
ans+=x[i][M-j-1];
uu[i].insert(M-j-1);
}
yy.push(make_pair(make_pair(0-x[i][M-k]-x[i][0],i),make_pair(M-k,0)));
}
for(i=0;i<M;i++) row.push_back(-1);
for(i=0;i<N;i++) answer.push_back(row);
//printf("%lld\n",ans);
while(1)
{
if(xx.empty()||yy.empty()) break;
aa=xx.top();
bb=yy.top();
xx.pop();
yy.pop();
if(aa.first.first+bb.first.first>0)
{
ans+=aa.first.first+bb.first.first;
//printf("%lld\n",ans);
uu[aa.first.second].erase(aa.second.first);
uu[aa.first.second].insert(aa.second.second);
aa.second.first--;
aa.second.second--;
if(aa.second.first>=0)
{
aa.first.first=x[aa.first.second][aa.second.first]+x[aa.first.second][aa.second.second];
xx.push(aa);
}
uu[bb.first.second].erase(bb.second.first);
uu[bb.first.second].insert(bb.second.second);
bb.second.first++;
bb.second.second++;
if(bb.second.first<M)
{
bb.first.first=0-x[bb.first.second][bb.second.first]-x[bb.first.second][bb.second.second];
yy.push(bb);
}
}
else break;
}
for(i=0;i<N;i++)
{
for(auto j:uu[i])
{
how.push_back(make_pair(x[i][j],make_pair(i,j)));
uu2[i].push_back(j);
}
}
sort(how.begin(),how.end());
for(i=0;i<N*k;i++) con[how[i].second.first][how[i].second.second]=i;
for(i=0;i<N;i++)
{
a[i]=0;
b[i]=k-1;
}
for(i=0;i<k;i++)
{
ll=0;
rr=0;
for(j=0;j<N;j++) use[j]=0;
for(j=0;j<N;j++)
{
if(a[j]<k&&con[j][uu2[j][a[j]]]>=N*k/2)
{
use[j]=1;
rr++;
answer[j][uu2[j][b[j]]]=i;
b[j]--;
}
if(b[j]>=0&&con[j][uu2[j][b[j]]]<N*k/2)
{
use[j]=1;
ll++;
answer[j][uu2[j][a[j]]]=i;
a[j]++;
}
}
for(j=0;j<N;j++)
{
if(use[j]) continue;
if(ll<N/2)
{
use[j]=1;
ll++;
answer[j][uu2[j][a[j]]]=i;
a[j]++;
}
else
{
use[j]=1;
rr++;
answer[j][uu2[j][b[j]]]=i;
b[j]--;
}
}
}
allocate_tickets(answer);
return ans;
}
