#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
long long n,m,fq[1569],od[1569][2];
pair<long long,long long> as[2250069];
long long find_maximum(int d,vector<vector<int>> a)
{
long long i,j,u,p,e,z=0;
vector<int> v;
vector<vector<int>> sq;
n=a.size();
m=a[0].size();
for(i=0;i<n;i++)
{
for(j=0;j<d;j++)
{
p=i*d+j;
as[p]={a[i][j]+a[i][j+m-d],i};
}
od[i][1]=m-1;
sq.push_back(v);
for(j=0;j<m;j++)
{
sq[i].push_back(-1);
}
}
sort(as,as+n*d);
for(i=0;i<n*d/2;i++)
{
p=as[i].sc;
fq[p]++;
}
for(i=0;i<d;i++)
{
for(j=0;j<n;j++)
{
as[j]={fq[j]-od[j][0],j};
}
sort(as,as+n,greater<pair<long long,long long>>());
for(j=0;j<n;j++)
{
p=as[j].sc;
e=j>=n/2;
u=!e*2-1;
z+=a[p][od[p][e]]*-u;
sq[p][od[p][e]]=i;
od[p][e]+=u;
}
}
allocate_tickets(sq);
return z;
}
