#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
void allocate_tickets( std::vector<std::vector<int>> _x);
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> answer(n,vector<int> (m,-1));
int r=0;
vector<pair<int,int>> q;
vector<pair<pair<int,int>,pair<int,int>>> add;
std::vector<int> p={};
for (int i = 0; i < n; i++) {
p.push_back(k-1);
for(int j=0;j<k;j++){
r-=x[i][j];answer[i][j]=1;
q.push_back({x[i][j]+x[i][m-(k-j)],add.size()});
add.push_back({{i,j},{i,m-(k-j)}});
}
}
sort(q.begin(),q.end());
int mn=10000000;
for(int z=n*k/2;z<n*k;z++){
r+=q[z].F;int i=q[z].S;
answer[add[i].F.F][add[i].F.S]=-1;
answer[add[i].S.F][add[i].S.S]=1;
mn=min(mn,x[add[i].S.F][add[i].S.S]);
}int d=-1;
for (int i = 0; i < n; i++){
int c=d+1;
for(int j=0;j<m;j++){
if(answer[i][j]==-1){
continue;
}
if(x[i][j]<mn)d=c;
answer[i][j]=c;
c=(c+1)%k;
}
}
allocate_tickets(answer);
return r;
}
