#include "tickets.h"
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer(n, vector<int>(m, -1));
long long prize = 0;
if (m == k) {
vector<int> cnt[2], remain[2];
cnt[0].resize(n), cnt[1].resize(n);
remain[0].resize(n), remain[1].resize(n);
vector<pair<int, int>> v;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) v.emplace_back(x[i][j], i);
}
sort(v.begin(), v.end());
for (int i = 0; (i<<1) < n*m; ++i) {
++cnt[0][v[i].second];
}
for (int i = 0; i < n; ++i) {
cnt[1][i] = m-cnt[0][i];
remain[0][i] = cnt[0][i];
remain[1][i] = cnt[1][i];
}
for (int i = 0; i < k; ++i) {
int used0 = 0;
for (int y = 0; y < n; ++y) {
if (!remain[1][y]) { // zero
prize -= x[y][cnt[0][y]-remain[0][y]];
answer[y][cnt[0][y]-remain[0][y]] = i;
--remain[0][y];
++used0;
} else if (!remain[0][y]) { // one
prize += x[y][cnt[0][y]+remain[1][y]-1];
answer[y][cnt[0][y]+remain[1][y]-1] = i;
--remain[1][y];
}
}
for (int y = 0; y < n; ++y) { // both
if (!remain[0][y] || !remain[1][y]) continue;
if (2*used0 < n) {
prize -= x[y][cnt[0][y]-remain[0][y]];
answer[y][cnt[0][y]-remain[0][y]] = i;
--remain[0][y];
++used0;
} else {
prize += x[y][cnt[0][y]+remain[1][y]-1];
answer[y][cnt[0][y]+remain[1][y]-1] = i;
--remain[1][y];
}
}
}
}
allocate_tickets(answer);
return prize;
}
