#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<ll>> f(n, vector<ll> (k + 1, 0));
vector<int> pluses(n);
vector<int> minuses(n);
set<pair<ll, int>> benefits;
ll mx = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < k; j++) f[i][0] -= x[i][j];
for(int r = 1; r <= k; r++){
f[i][r] = f[i][r - 1] + x[i][m - r] + x[i][k - r]; // f is concave :)
}
benefits.insert({f[i][1] - f[i][0], i});
minuses[i] = k;
mx += f[i][0];
}
for(int r = 1; r <= (n * k) / 2; r++){
auto it = *benefits.rbegin();
benefits.erase(it);
int i = it.second;
mx += it.first;
pluses[i]++;
minuses[i]--;
if(pluses[i] != k) benefits.insert({f[i][pluses[i] + 1] - f[i][pluses[i]], i});
}
vector<vector<int>> when(n, vector<int>(m, -1));
for(int r = 0; r < k; r++){
// choose n / 2 pluses, n / 2 minuses
vector<int> perm(n, 0);
iota(perm.begin(), perm.end(), 0);
vector<int> hasOption(n);
for(int i = 0; i < n; i++) hasOption[i] = pluses[i] && minuses[i];
sort(perm.begin(), perm.end(), [&](int i, int j){return hasOption[i] < hasOption[j];});
int balance = 0;
for(int i : perm){
if(balance <= 0){
if(pluses[i]){
when[i][m - pluses[i]] = r;
pluses[i]--;
balance++;
} else{
when[i][--minuses[i]] = r;
balance--;
}
} else{
if(minuses[i]){
when[i][--minuses[i]] = r;
balance--;
} else{
when[i][m - pluses[i]] = r;
pluses[i]--;
balance++;
}
}
}
assert(balance == 0);
}
allocate_tickets(when);
return mx;
}
