#include "tickets.h"
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix= vector<vector<T>>;
struct ticket{
int val, id, col;
bool operator<(ticket b) const{
return val < b.val;
}
};
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
matrix<int> resp(n,vector<int>(m,-1));
for(int i = 0; i < n; i++){
iota(resp[i].begin(),resp[i].begin()+k,0);
}
multiset<ticket> minus, plus;
ll ans = 0;
for(int i = 0; i < n/2; i++){
for(int j = 0; j < k; j++){
minus.insert({-x[i][j],i,j});
ans-=x[i][j];
}
}
for(int i = n/2; i < n; i++){
for(int j = 0; j < k; j++){
plus.insert({x[i][j],i,j});
ans+=x[i][j];
}
}
vector<int> o(n);
iota(all(o),0);
sort(all(o),[&](int a, int b){
return resp[a][0]+resp[a][1] > resp[b][0]+resp[b][1];
});
while(minus.begin()->val > plus.begin()->val*-1){
ticket t1 = *minus.begin(), t2 = *plus.begin();
minus.erase(minus.begin());
plus.erase(plus.begin());
swap(resp[t1.id][t1.col],resp[t2.id][t2.col]);
ans+=t1.val*-2;
ans+=t2.val*-2;
t1.val*=-1;
t2.val*=-1;
plus.insert(t1);
minus.insert(t2);
}
allocate_tickets(resp);
return ans;
}
