#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
typedef long long ll;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
ll ret=0;
vector<vector<int> > ans(n,vector<int>(m,-1));
vector<pair<int,int> > v,v2;
for(int i=0;i<n/2;i++){
for(int j=0;j<k;j++){
v.push_back({x[i][j]+x[i][j+(m-k)],i});
ret-=x[i][j];
}
}
for(int i=n/2;i<n;i++){
for(int j=m-k;j<m;j++){
v2.push_back({x[i][j]+x[i][j-(m-k)],i});
ret+=x[i][j];
}
}
sort(v.begin(),v.end(),greater<pair<int,int> >());
sort(v2.begin(),v2.end());
vector<pair<int,int> > nw(n);
for(int i=0;i<n;i++){
nw[i].sc=i;
}
for(int i=0;i<n/2;i++){
nw[i].fs=k;
}
for(int i=0;i<n*k/2;i++){
if(v[i].fs>v2[i].fs){
nw[v[i].sc].fs--;
nw[v2[i].sc].fs++;
ret+=(v[i].fs-v2[i].fs);
}
}
vector<int> l(n),r(n,m-1);
for(int i=0;i<k;i++){
sort(nw.begin(),nw.end(),greater<pair<int,int> >());
for(int j=0;j<n/2;j++){
ans[nw[j].sc][l[nw[j].sc]]=i;
nw[j].fs--;
l[nw[j].sc]++;
}
for(int j=n/2;j<n;j++){
ans[nw[j].sc][r[nw[j].sc]]=i;
r[nw[j].sc]--;
}
}
/*
vector<int> l(n),r(n,m-1);
for(int w=0;w<k;w++){
vector<pair<int,int> > v;
for(int i=0;i<n;i++){
v.push_back({x[i][l[i]]+x[i][r[i]],i});
}
sort(v.begin(),v.end());
for(int i=0;i<n/2;i++){
ret-=x[v[i].sc][l[v[i].sc]];
ans[v[i].sc][l[v[i].sc]]=w;
l[v[i].sc]++;
ret+=x[v[i+n/2].sc][r[v[i+n/2].sc]];
ans[v[i+n/2].sc][r[v[i+n/2].sc]]=w;
r[v[i+n/2].sc]--;
}
}
*/
allocate_tickets(ans);
return ret;
}
