#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer;
vector<int> r(n, 0);
ll Sum = 0;
priority_queue<pair<ll,int>> q;
for (int i = 0; i < n; i++) {
vector<int> row(m);
for (int j = 0; j < m; j++) {
if (j < k) {
row[j] = j;
Sum -= x[i][j];
} else {
row[j] = -1;
}
}
q.push({x[i][k - 1] + x[i][m - 1], i});
answer.push_back(row);
}
for (int rep = 0 ; rep < k * n / 2 ; ++ rep) {
auto [val, i] = q.top(); q.pop();
//if (k - 1 - r[i] == m - 1 - r[i]) val /= 2;
Sum += val;
answer[i][k - 1 - r[i]] = -1;
answer[i][m - 1 - r[i]] = k - 1 - r[i];
r[i]++;
}
//cout << Sum << "\n";
//for (auto vec : answer) { for (int i : vec) cout << i << " "; cout << "\n"; }
allocate_tickets(answer);
return Sum;
}
