#include "tickets.h"
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
#define int long long
using namespace std;
long long find_maximum(signed k, vector<vector<signed>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<signed>> answer (n, vector<signed> (m, -1));
int ans = 0;
vector<int> cuts (n, 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (x[i][j] == 0) cuts[i] = j + 1;
}
}
vector<int> oprov (n);
iota(oprov.begin(), oprov.end(), 0);
sort(oprov.begin(), oprov.end(), [&](int a, int b){return cuts[a] > cuts[b];});
int uz = 0, uo = 0;
for (int i = 0; i < n/2; ++i) {
uz += min(cuts[oprov[i]], (int)k);
}
for (int i = n/2; i < n; ++i) {
uo += min(m - cuts[oprov[i]], (int)k);
}
ans = min(uz, uo);
for (int i = 0; i < k; ++i) {
for (int j = 0; j < n / 2; ++j) {
answer[oprov[j]][i] = i;
}
for (int j = n/2; j < n; ++j) {
answer[oprov[j]][m-i-1] = i;
}
}
allocate_tickets(answer);
return ans;
}
