#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
priority_queue<pair<int, int>> pqai3;
vector<vector<int>> vvi(n, vector<int>(m, 1));
vector<int> l(n), r(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++)
vvi[i][j] = 0;
l[i] = k - 1, r[i] = m - 1;
}
for (int i = 0; i < n; i++)
pqai3.emplace(x[i][l[i]] + x[i][r[i]], i);
for (int i = 0; i < n / 2 * k; i++) {
auto [add, in] = pqai3.top();
// cout << add << " " << in << "\n";
pqai3.pop();
vvi[in][l[in]] = 1;
vvi[in][r[in]] = 2;
r[in]--, l[in]--;
if (l[in] > 0) {
pqai3.emplace(x[in][l[in]] + x[in][r[in]], in);
}
}
vector<vector<int>> ans(n, vector<int>(m, -1));
vector<int> all(n);
iota(all.begin(), all.end(), 0);
vector<int> twos(n);
for (int i = 0; i < n; i++) {
l[i] = 0, r[i] = m - 1;
for (int j = 0; j < n; j++) {
if (vvi[i][j] == 2)
twos[i]++;
}
}
for (int i = 0; i < k; i++) {
sort(all.begin(), all.end(),
[&](int a, int b) { return twos[a] < twos[b]; });
for (int j = 0; j < n / 2; j++) {
ans[all[j]][l[all[j]]++] = i;
}
for (int j = n / 2; j < n; j++) {
twos[all[j]]--;
ans[all[j]][r[all[j]]--] = i;
}
}
allocate_tickets(ans);
long long tot = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//cout << i << ' ' << j << " " << vvi[i][j] << " " << x[i][j] << "\n";
if (vvi[i][j] == 0)
tot -= x[i][j];
else if (vvi[i][j] == 2)
tot += x[i][j];
}
}
return tot;
}
