#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000002022;
int inf=1000000007;
ll infl=1000000000000000007;
/*void allocate_tickets(vector<vector<int>>r)
{
int n=sz(r),m=sz(r[0]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++) cout<<r[i][j]<<" ";
cout<<endl;
}
}*/
ll find_maximum(int k,vector<vector<int>>a)
{
int n=sz(a),m=sz(a[0]);
vector<pair<int,pair<int,int>>>V;
vector<vector<int>>r(n,vector<int>(m,-1));
ll sum=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++) V.pb({a[i][j],{i,j}});
for(int j=m-k;j<m;j++) sum+=a[i][j];
}
sort(all(V));
set<pair<int,pair<int,int>>>good,bad;
ll ans=-infl,act=0;
int ile=n*k/2,ii,jj;
for(auto [q,p]:V)
{
int i=p.st,j=p.nd;
if(j<k)
{
act+=-a[i][j]-a[i][m-k+j];
good.insert({-a[i][j]-a[i][m-k+j],{i,j}});
}
if(j>=m-k)
{
ile--;
if(!good.erase({-a[i][j]-a[i][j-m+k],{i,j-m+k}}))
{
bad.erase({-a[i][j]-a[i][j-m+k],{i,j-m+k}});
act+=-a[i][j]-a[i][j-m+k];
}
}
if(ile<0) break;
while(sz(good)>ile)
{
act-=(*good.begin()).st;
bad.insert(*good.begin());
good.erase(*good.begin());
}
while(sz(bad)>0&&sz(good)<ile)
{
act+=(*--bad.end()).st;
good.insert(*--bad.end());
bad.erase(*--bad.end());
}
if(sz(good)==ile&&act>ans)
{
ans=act;
ii=i;
jj=j;
}
}
good.clear(),bad.clear();
ile=n*k/2;
vector<int>X(n,-1),Y(n,m-k);
for(auto [q,p]:V)
{
int i=p.st,j=p.nd;
if(j<k)
{
good.insert({-a[i][j]-a[i][m-k+j],{i,j}});
}
if(j>=m-k)
{
ile--;
X[i]++;
Y[i]--;
if(!good.erase({-a[i][j]-a[i][j-m+k],{i,j-m+k}}))
{
bad.erase({-a[i][j]-a[i][j-m+k],{i,j-m+k}});
}
}
if(ile<0) break;
while(sz(good)>ile)
{
act-=(*good.begin()).st;
bad.insert(*good.begin());
good.erase(*good.begin());
}
while(sz(bad)>0&&sz(good)<ile)
{
act+=(*--bad.end()).st;
good.insert(*--bad.end());
bad.erase(*--bad.end());
}
if(i==ii&&j==jj)
{
for(auto x:good)
{
X[x.nd.st]++;
Y[x.nd.st]++;
}
break;
}
}
for(int j=0;j<k;j++)
{
int c1=n/2,c2=n/2;
for(int i=0;i<n;i++)
{
if(X[i]==-1)
{
c2--;
r[i][Y[i]]=j;
Y[i]++;
}
else if(Y[i]==m)
{
c1--;
r[i][X[i]]=j;
X[i]--;
}
}
for(int i=0;i<n;i++)
{
if(X[i]!=-1&&c1>0)
{
c1--;
r[i][X[i]]=j;
X[i]--;
}
else
{
c2--;
r[i][Y[i]]=j;
Y[i]++;
}
}
}
allocate_tickets(r);
return ans+sum;
}
