#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
long long find_maximum(int k, vector<vector<int>> a) {
int n=a.size(), m=a[0].size();
int cnt[n]={}, f[n], l[n];
ll ans=0, pre[n][m+1]={};
if (k==m)
{
vector<pair<int,int>> r;
for (int i=0;i<n;i++)
for (int x:a[i])
r.push_back({x,i});
sort(all(r));
int cnt[n]={}, f[n], l[n];
for (int i=0;i<n;i++)
f[i]=0, l[i]=m-1;
for (int i=0;i<n*m;i++)
if (i<n*m/2) ans-=r[i].first;
else ans+=r[i].first, cnt[r[i].second]++;
vector<vector<int>> b(n,vector<int>(m,-1));
vector<pair<int,int>> v;
for (int i=0;i<n;i++) v.push_back({cnt[i],i});
for (int ct=0;ct<k;ct++)
{
sort(all(v));
for (int i=0;i<n;i++)
if (i<n/2) b[v[i].second][f[v[i].second]++]=ct;
else b[v[i].second][l[v[i].second]--]=ct, cnt[v[i].second]--;
v.clear();
for (int i=0;i<n;i++) v.push_back({cnt[i],i});
}
allocate_tickets(b);
return ans;
}
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
pre[i][j+1]=pre[i][j]+a[i][j];
set<pair<int,int>> se,se1;
for (int i=0;i<n;i++)
if (i<n/2)
ans-=pre[i][k], se.insert({a[i][m-1]+a[i][k-1],i}), cnt[i]=0;
else
ans+=pre[i][m]-pre[i][m-k], se1.insert({-a[i][m-k]-a[i][0],i}), cnt[i]=k;
while (se.size() && se1.size())
{
pair<int,int> p=*se.rbegin(), p1=*se1.rbegin();
if (1ll*p.first+p1.first<=0) break;
ans+=1ll*p.first+p1.first, se.erase(p), se1.erase(p1);
int i=p.second, j=p1.second;
cnt[i]++, cnt[j]--;
if (cnt[i]<k)
se.insert({a[i][m-1-cnt[i]]+a[i][k-cnt[i]-1],i});
if (cnt[j])
se1.insert({-a[j][m-cnt[j]]-a[j][k-cnt[j]],j});
}
for (int i=0;i<n;i++)
f[i]=0, l[i]=m-1;
vector<vector<int>> b(n,vector<int>(m,-1));
vector<pair<int,int>> v;
for (int i=0;i<n;i++) v.push_back({cnt[i],i});
for (int ct=0;ct<k;ct++)
{
sort(all(v));
for (int i=0;i<n;i++)
if (i<n/2) b[v[i].second][f[v[i].second]++]=ct;
else b[v[i].second][l[v[i].second]--]=ct, cnt[v[i].second]--;
v.clear();
for (int i=0;i<n;i++) v.push_back({cnt[i],i});
}
allocate_tickets(b);
return ans;
}
