#include "tickets.h"
#include <vector>
#include <algorithm>
#include <tuple>
#include <cassert>
#include <iostream>
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) {
vector<int> zero, one, both;
for (int j = 0; j < n; ++j) {
if (!remain[1][j]) zero.push_back(j);
else if (!remain[0][j]) one.push_back(j);
else both.push_back(j);
}
assert(2*(int)zero.size() <= n);
assert(2*(int)one.size() <= n);
vector<int> u;
u.insert(u.end(), zero.begin(), zero.end());
u.insert(u.end(), both.begin(), both.end());
u.insert(u.end(), one.begin(), one.end());
int used0 = 0;
for (int y : u) {
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;
}
