#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, k;
set<pair<int, int>> add0, add1;
void Add0(int i, vector<int>& zeros, vector<int>& ones, vector<vector<int>>& x){
if(zeros[i] < k) add0.insert({x[i][zeros[i]] + x[i][m-ones[i]], i});
}
void Add1(int i, vector<int>& zeros, vector<int>& ones, vector<vector<int>>& x){
if(zeros[i] > 0) add1.insert({x[i][zeros[i]-1] + x[i][m-ones[i]-1], i});
}
void Erase0(int i, vector<int>& zeros, vector<int>& ones, vector<vector<int>>& x){
if(zeros[i] < k) add0.erase({x[i][zeros[i]] + x[i][m-ones[i]], i});
}
void Erase1(int i, vector<int>& zeros, vector<int>& ones, vector<vector<int>>& x){
if(zeros[i] > 0) add1.erase({x[i][zeros[i]-1] + x[i][m-ones[i]-1], i});
}
long long find_maximum(int _k, vector<vector<int>> x) {
k = _k;
n = (int)x.size();
m = (int)x[0].size();
vector<int> zeros(n, k/2), ones(n, k - k/2);
add0.clear(); add1.clear();
for(int i = 0; i < n; i++){
if(i%2 && k%2) {zeros[i]++; ones[i]--;}
//To convert 1 to 0, I substract the sum of both.
//To convert 0 to 1, I add the sum of both.
Add0(i, zeros, ones, x);
Add1(i, zeros, ones, x);
//If I already have chosen k, it is the same element that I am adding twice.
}
//So, at each time, I convert one from 0 to 1 and one from 1 to 0. The ones from 1 to 0 I substract.
while((*add1.rbegin()).first - (*add0.begin()).first > 0){
int ind1 = (*add1.rbegin()).second; add1.erase(*add1.rbegin());
int ind0 = (*add0.begin()).second; add0.erase(add0.begin());
Erase0(ind1, zeros, ones, x);
Erase1(ind0, zeros, ones, x);
zeros[ind1]--; ones[ind1]++; zeros[ind0]++; ones[ind0]--;
Add0(ind0, zeros, ones, x);
Add1(ind0, zeros, ones, x);
Add0(ind1, zeros, ones, x);
Add1(ind1, zeros, ones, x);
}
ll res = 0;
for(int i = 0; i < n; i++){
// cout << "i " << i << " zeros " << zeros[i] << " ones " << ones[i] << "\n";
for(int j = 0; j < zeros[i]; j++) res -= x[i][j];
for(int j = m - ones[i]; j < m; j++) res += x[i][j];
}
vector<vector<int>> ans(n, vector<int>(m, -1));
vector<pair<int, int>> rng(n);
for(int i = 0; i < n; i++){
rng[i] = {zeros[i]-1, m-1}; //The starting index from which I go down for each of them.
}
for(int r = 0; r < k; r++){
vector<pair<int, int>> ordOne(n);
for(int i = 0; i < n; i++){
ordOne[i] = {ones[i], i};
}
sort(ordOne.begin(), ordOne.end());
for(int i = n/2; i < n; i++){
int row = ordOne[i].second;
ones[row]--;
ans[row][rng[row].second] = r;
rng[row].second--;
}
for(int i = 0; i < n/2; i++){
int row = ordOne[i].second;
zeros[row]--;
ans[row][rng[row].first] = r;
rng[row].first--;
}
}
allocate_tickets(ans);
return res;
}
