#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;
ticket();
ticket(int a, int b, int c){
val = a, id = b, col = c;
}
bool operator<(ticket b) const{
return make_tuple(val,id,col) < make_tuple(b.val,b.id,b.col);
}
};
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);
}
set<ticket> minus, plus;
ll ans = 0;
ll bestans = 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][m-1] > resp[b][m-1];
});
while(minus.begin()->val*-1 > plus.begin()->val){
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);
}
bestans = ans;
for(int i : o){
if(minus.count(ticket(x[i][0],i,0))){
ans+=x[i][0];
minus.erase(ticket(x[i][0],i,0));
ans-=x[i][m-1];
swap(resp[i][0],resp[i][m-1]);
minus.insert(ticket(x[i][m-1],i,m-1));
} else {
ans-=x[i][0];
plus.erase(ticket(x[i][0],i,0));
ans+=x[i][m-1];
swap(resp[i][0],resp[i][m-1]);
plus.insert(ticket(x[i][m-1],i,m-1));
}
while(minus.begin()->val*-1 > plus.begin()->val){
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);
}
bestans = max(ans,bestans);
}
//cout << "->" << bestans<< '\n';
{
minus.clear();
plus.clear();
for(int i = 0; i < n; i++){
iota(resp[i].begin(),resp[i].begin()+k,0);
}
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][m-1] > resp[b][m-1];
});
while(minus.begin()->val*-1 > plus.begin()->val){
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);
}
if(ans == bestans){
allocate_tickets(resp);
}
return ans;
for(int i : o){
//cout << ans << '\n';
if(minus.count(ticket(x[i][0],i,0))){
ans+=x[i][0];
minus.erase(ticket(x[i][0],i,0));
ans-=x[i][m-1];
swap(resp[i][0],resp[i][m-1]);
minus.insert(ticket(x[i][m-1],i,m-1));
} else {
ans-=x[i][0];
plus.erase(ticket(x[i][0],i,0));
ans+=x[i][m-1];
swap(resp[i][0],resp[i][m-1]);
plus.insert(ticket(x[i][m-1],i,m-1));
}
while(minus.begin()->val*-1 > plus.begin()->val){
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);
}
//cout << ans << '\n';
if(ans == bestans){
allocate_tickets(resp);
}
return ans;
}
}
allocate_tickets(resp);
return ans;
}
