#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<vector<int>> ans(n, vector<int>(m, -1));
vector<pair<int, int>> rng(n, {0, m-1});
long long res = 0;
for(int r = 0; r < k; r++){
vector<pair<long long, int>> difs;
for (int i = 0; i < n; i++) {
difs.push_back({x[i][rng[i].second] + x[i][rng[i].first], i});
}
sort(difs.begin(), difs.end());
for (int i = 0; i < n/2; i++) {
//These substract.
res -= x[i][rng[i].first];
ans[i][rng[i].first] = r;
rng[i].first++;
}
for (int i = 0; i < n/2; i++) {
//These substract.
res += x[i][rng[i].second];
ans[i][rng[i].second] = r;
rng[i].second--;
}
}
allocate_tickets(ans);
return res;
}
