#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using i64 = long long;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
assert(k == 1);
i64 S = 0;
std::vector ans(n, std::vector<int>(m, -1));
for (int i = 0; i < n; i++) {
ans[i][0] = 0;
S -= x[i][0];
}
std::vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int i, int j) {
return x[i][0] + x[i][m - 1] > x[j][0] + x[j][m - 1];
});
ord.resize(n / 2);
for (int i : ord) {
ans[i][0] = -1;
ans[i][m - 1] = 0;
S += x[i][0] + x[i][m - 1];
}
allocate_tickets(ans);
return S;
}
