#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, m - 1), l(n, k - 1), cnt(k, 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 done = 0 ; done < k * n / 2 ; ) {
auto [val, i] = q.top(); q.pop();
if (cnt[l[i]] < n / 2) {
if (l[i] == r[i]) val /= 2;
Sum += val;
cnt[l[i]]++;
answer[i][l[i]] = -1;
answer[i][r[i]] = l[i];
r[i]--;
++done;
}
l[i]--;
if (l[i] >= 0) {
q.push({x[i][l[i]] + x[i][r[i]], i});
}
}
//cout << Sum << "\n";
//for (auto vec : answer) { for (int i : vec) cout << i << " "; cout << "\n"; }
allocate_tickets(answer);
return Sum;
}
