#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
typedef long long ll;
#define pb push_back
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
// think in terms of change;
vector<array<int, 3>> change;
ll sum = 0;
REP(i, n){
REP(j, k){
change.pb({x[i][j] + x[i][m - k + j], i, j});
sum -= x[i][j];
}
}
sort(change.begin(), change.end(), greater<array<int, 3>>());
vector<int> upper(n, k);
vector<vector<array<int, 2>>> rows(n);
REP(i, n * k / 2){
auto v = change[i];
sum += v[0];
upper[v[1]] = v[2];
}
REP(i, n){
REP(j, upper[i]){
rows[i].pb({x[i][j], j});
}
}
REP(i, n){
REP(j, k - upper[i]){
rows[i].pb({x[i][m - 1 - j], m - 1 - j});
}
}
vector<int> cnts = upper; // cnt smaller available
vector<vector<int>> answer(n, vector<int>(m, -1));
vector<int> sorted(n);
iota(sorted.begin(), sorted.end(), 0);
auto cmp = [&](int f, int s){
return cnts[f] > cnts[s];
};
REP(i, k){
sort(sorted.begin(), sorted.end(), cmp);
REP(j, n / 2){
cnts[sorted[j]]--;
int row = sorted[j]; int col = rows[row][cnts[row]][1];
answer[row][col] = i;
}
FOR(j, n / 2, n, 1){
int row = sorted[j];
int smaller_taken = upper[row] - cnts[row];
int col = k - 1 - i + smaller_taken;
col = rows[row][col][1];
answer[row][col] = i;
}
}
allocate_tickets(answer);
return sum;
}
