#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));
for(int i = 0; i < n; i++){
iota(all(resp[i]),0);
}
priority_queue<ticket> minus, plus;
ll ans = 0;
for(int i = 0; i < n/2; i++){
for(int j = 0; j < m; j++){
minus.push({x[i][j],i,j});
ans-=x[i][j];
}
}
for(int i = n/2; i < n; i++){
for(int j = 0; j < m; j++){
plus.push({-x[i][j],i,j});
ans+=x[i][j];
}
}
while(minus.top().val > plus.top().val*-1){
ticket t1 = minus.top(), t2 = plus.top();
minus.pop();
plus.pop();
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.push(t1);
minus.push(t2);
}
allocate_tickets(resp);
return ans;
}
