#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
struct IMPROVEMENT{
int lin,col,val;
bool operator<(IMPROVEMENT ot){
return val>ot.val;
}
};
struct AVAILABLE{
int lin,cnt;
bool operator<(AVAILABLE ot){
return cnt>ot.cnt;
}
};
long long find_maximum(int k,vector<vector<int>>x){
int n = x.size();
int m = x[0].size();
long long sum=0;
int i,j;
vector<IMPROVEMENT>improvement;
vector<vector<int>>answer;
for(i=0;i<n;++i){
for(j=0;j<k;++j)
sum-=x[i][j];
for(j=m-1;j>=m-k;--j)
improvement.push_back({i,j,x[i][j]+x[i][k-m+j]});
vector<int>row;
for(j=0;j<m;++j)
row.push_back(-1);
answer.push_back(row);
}
sort(improvement.begin(),improvement.end());
vector<AVAILABLE>available(n);
for(i=0;i<n;++i)
available[i]={i,k};
for(i=0;i<n*k/2;++i){
sum+=improvement[i].val;
--available[improvement[i].lin].cnt;
}
for(i=0;i<k;++i){
sort(available.begin(),available.end());
for(j=0;j<n;++j)
if(j<n/2){
answer[available[j].lin][available[j].cnt-1]=i;
--available[j].cnt;
}
else
answer[available[j].lin][m-k+i+available[j].cnt]=i;
}
allocate_tickets(answer);
return sum;
}
