#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k,vector <vector <int> > x){
int n=x.size(),m=x[0].size();
vector <vector <int> > op(n,vector <int>(m,-1));
int chkmx=0;
for (int i=0; i<n; i++) for (int j=0; j<m; j++) chkmx=max(chkmx,x[i][j]);
long long ans=0;
if (k==1){
int idxmn[n],idxmx[n];
for (int i=0; i<n; i++){
idxmn[i]=min_element(x[i].begin(),x[i].end())-x[i].begin();
idxmx[i]=max_element(x[i].begin(),x[i].end())-x[i].begin();
}
long long dp[n+1][n+1],bac[n+1][n+1];
for (int i=0; i<=n; i++){
for (int j=0; j<=n; j++) dp[i][j]=-1e18;
}
dp[0][0]=0;
for (int i=0; i<n; i++){
for (int j=0; j<=n/2; j++){
if (dp[i][j]-x[i][idxmn[i]]>=dp[i+1][j]){
dp[i+1][j]=dp[i][j]-x[i][idxmn[i]];
bac[i+1][j]=0;
}
if (dp[i][j]+x[i][idxmx[i]]>=dp[i+1][j+1]){
dp[i+1][j+1]=dp[i][j]+x[i][idxmx[i]];
bac[i+1][j+1]=1;
}
}
}
ans=dp[n][n/2];
int cur=n/2;
for (int i=n; i>0; i--){
if (bac[i][cur]){
op[i-1][idxmx[i-1]]=0;
cur--;
} else {
op[i-1][idxmn[i-1]]=0;
}
}
} else if (chkmx<=1){
int bal[n];
for (int i=0; i<n; i++){
bal[i]=0;
for (int j=0; j<m; j++){
if (!x[i][j]) bal[i]--;
else bal[i]++;
}
}
int fr[n],ba[n];
for (int i=0; i<n; i++) fr[i]=0;
for (int i=0; i<n; i++) ba[i]=m-1;
for (int i=0; i<k; i++){
vector <pair <int,int> > v;
for (int j=0; j<n; j++) v.push_back({bal[j],j});
sort(v.begin(),v.end());
for (int j=0; j<n; j++){
if (j<n/2){
op[v[j].second][fr[v[j].second]]=i;
if (!x[v[j].second][fr[v[j].second]]) bal[v[j].second]++;
else bal[v[j].second]--;
ans-=x[v[j].second][fr[v[j].second]];
fr[v[j].second]++;
} else {
op[v[j].second][ba[v[j].second]]=i;
if (x[v[j].second][ba[v[j].second]]) bal[v[j].second]--;
else bal[v[j].second]++;
ans+=x[v[j].second][ba[v[j].second]];
ba[v[j].second]--;
}
}
}
} else if (k==m){
vector <pair <long long,pair <int,int> > > v;
for (int i=0; i<n; i++) for (int j=0; j<m; j++) v.push_back({x[i][j],{i,j}});
sort(v.begin(),v.end());
for (int i=0; i<n*m; i++){
if (i<n*m/2) ans-=v[i].first;
else ans+=v[i].first;
}
bool is[n][m];
for (int i=0; i<n; i++) for (int j=0; j<m; j++) is[i][j]=0;
for (int i=n*m/2; i<n*m; i++) is[v[i].second.first][v[i].second.second]=1;
int idx=0;
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
if (is[i][j]){
op[i][j]=idx;
idx++;
if (idx>=m) idx-=m;
}
}
}
bool hv[m];
for (int i=0; i<n; i++){
for (int j=0; j<m; j++) hv[j]=0;
for (int j=0; j<m; j++) if (op[i][j]>=0) hv[op[i][j]]=1;
int ptr=0;
for (int j=0; j<m; j++){
if (op[i][j]==-1){
while (hv[ptr]) ptr++;
op[i][j]=ptr;
ptr++;
}
}
}
}
allocate_tickets(op);
return ans;
}
