#include <bits/stdc++.h>
#include "tickets.h"
#include <vector>
#define pb push_back
using namespace std;
typedef long long ll;
ll find_maximum(int k, vector<vector<int>> x) {
ll n = x.size();
ll m = x[0].size();
vector<vector<int>> answer;
ll ans=0;
if(m==1){
vector<ll> a;
for(ll i=0;i<n;i++){
a.pb(x[i][0]);
}
sort(a.begin(),a.end());
for(ll i=0;i<n;i++){
ans+=abs(a[i]-a[n/2]);
}
for(ll i=0;i<n;i++){
answer.pb({0});
}
}
else{
for(ll i=0;i<n;i++){
vector<int> d;
for(ll j=0;j<m;j++){
d.pb(-1);
}
answer.pb(d);
}
for(int z=0;z<k;z++){
ll res=-1;
ll ind=0;
ll l[n],f[n],l1[n],f1[n];
vector<array<ll,3>> c;
for(ll i=0;i<n;i++){
for(ll j=0;j<m;j++){
if(answer[i][j]==-1){
c.pb({x[i][j],i,j});
l[i]=x[i][j];
l1[i]=j;
}
}
for(ll j=m-1;j>=0;j--){
if(answer[i][j]==-1){
f[i]=x[i][j];
f1[i]=j;
}
}
}
sort(c.begin(),c.end());
set<pair<ll,ll>> s1,s2;
ll cnt=0;
ll sum1=0,sum2=0,sum3=0;
ll sz=(ll)c.size();
for(ll i=0;i<n;i++){
sum3+=l[i];
}
for(ll i=0;i<sz;i++){
if(n/2-cnt<0){
break;
}
if(c[i][2]==l1[c[i][1]]){
pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if(s1.find(p)!=s1.end()){
s1.erase(p);
sum2-=p.first;
}
else{
s2.erase(p);
}
}
ll res1=0;
if((ll)s1.size()==n/2-cnt){
ll sum=sum2;
pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if(s1.find(p)!=s1.end()){
if((ll)s2.size()!=0){
sum-=p.first;
p=*(--s2.end());
sum+=p.first;
sum3-=l[c[i][1]];
res1=sum3-(n-cnt-1)*c[i][0]+2*c[i][0]*(n/2-cnt)+sum+cnt*c[i][0]-sum1;
sum3+=l[c[i][1]];
}
}
else{
sum3-=l[c[i][1]];
res1=sum3-(n-cnt-1)*c[i][0]+2*c[i][0]*(n/2-cnt)+sum+cnt*c[i][0]-sum1;
sum3+=l[c[i][1]];
}
}
if(c[i][2]==f1[c[i][1]]){
pair<ll,ll> p=*(s1.begin());
pair<ll,ll> nw={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if((ll)s1.size()<n/2-cnt){
s1.insert(nw);
sum2+=nw.first;
}
else{
if(nw.first>p.first){
s1.erase(p);
s1.insert(nw);
s2.insert(p);
sum2-=p.first;
sum2+=nw.first;
}
else{
s2.insert(nw);
}
}
}
if(c[i][2]==l1[c[i][1]]){
cnt++;
sum1+=f[c[i][1]];
if((ll)s1.size()>n/2-cnt){
pair<ll,ll> h=*(s1.begin());
s1.erase(h);
s2.insert(h);
sum2-=h.first;
}
sum3-=l[c[i][1]];
}
if(res1>res){
res=res1;
ind=i;
}
}
cnt=0;
s1.clear();
s2.clear();
for(ll i=0;i<=ind;i++){
if(n/2-cnt<0){
break;
}
if(c[i][2]==l1[c[i][1]]){
pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if(s1.find(p)!=s1.end()){
s1.erase(p);
}
else{
s2.erase(p);
}
}
if(i==ind){
pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
for(auto x:s1){
if(x.second!=c[i][1]){
answer[x.second][f1[x.second]]=z;
}
}
if(s1.find(p)!=s1.end()){
if((ll)s2.size()==0){
continue;
}
p=*(--s2.end());
answer[p.second][f1[p.second]]=z;
}
for(ll j=0;j<n;j++){
if(j==c[i][1]){
answer[c[i][1]][c[i][2]]=z;
continue;
}
if(answer[j][f1[j]]==-1 && answer[j][l1[j]]==-1){
answer[j][l1[j]]=z;
}
}
break;
}
if(c[i][2]==f1[c[i][1]]){
pair<ll,ll> p=*(s1.begin());
pair<ll,ll> nw={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if((ll)s1.size()<n/2-cnt){
s1.insert(nw);
}
else{
if(nw.first>p.first){
s1.erase(p);
s1.insert(nw);
s2.insert(p);
}
else{
s2.insert(nw);
}
}
}
if(c[i][2]==l1[c[i][1]]){
answer[c[i][1]][f1[c[i][1]]]=z;
cnt++;
if((ll)s1.size()>n/2-cnt){
pair<ll,ll> h=*(s1.begin());
s1.erase(h);
s2.insert(h);
}
}
}
ans+=res;
}
}
allocate_tickets(answer);
return ans;
}
