#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
int dod[n];
int uj[n];
int ile[n];
int gora[n];
int dol[n];
rep(i, n) {
ile[i] = 0;
dod[i] = 0;
dol[i] = 0;
gora[i] = m - 1;
uj[i] = k;
}
priority_queue<pair<ll, int>> pq;
ll ans = 0;
rep(i, n) {
rep(j, k) {
ans -= x[i][j];
}
}
rep(i, n) {
rep(j, k) {
pq.push({x[i][m - 1 - j] + x[i][k - 1 - j], i});
}
}
ll pom = (k * n)/2;
while (pom--) {
pair<ll, int> p = pq.top();
pq.pop();
if (ile[p.nd] == k) continue;
ile[p.nd]++;
dod[p.nd]++;
uj[p.nd]--;
ans += p.st;
}
vector<vector<int>> s;
rep(i, n) {
s.pb({});
rep(j, m) {
s[i].pb(-1);
}
}
rep(r, k) {
vector<pair<int, int>> vec;
rep(i, n) {
vec.pb({uj[i], i});
}
sort(vec.begin(), vec.end());
int n2 = n/2;
rep(i, n2) {
int it = vec[i].nd;
s[it][gora[it]] = r;
dod[it]--;
gora[it]--;
}
for (int i = n2; i < n; i++) {
int it = vec[i].nd;
s[it][dol[it]] = r;
uj[it]--;
dol[it]++;
}
}
allocate_tickets(s);
return ans;
}
