#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> resp(m, -1);
answer.push_back(resp);
}
vector<deque<pair<int, int>>> q(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
q[i].push_back({x[i][j], j});
}
}
long long resp = 0;
for (int i = 0; i < k; i++) {
vector<int> amt(2, 0);
for (int j = 0; j < n; j++) {
if (q[j].front().first == 0) amt[0]++;
if (q[j].back().first == 1) amt[1]++;
}
for (int j = 0; j < n; j++) {
for (auto k : q[j]) {
//cerr << k.first << ' ';
}
//cerr << '\n';
}
//cerr << "kys " << amt[0] << ' ' << amt[1] << '\n';
if (amt[0] >= n / 2 && amt[1] >= n / 2) {
vector<bool> used(n, 0);
int need = n / 2;
resp += n / 2;
for (int j = 0; j < n; j++) {
if (need == 0) break;
auto [elm, idx] = q[j].front();
if (elm == 1) continue;
answer[j][idx] = i;
q[j].pop_front();
used[j] = 1;
need--;
}
cout << "used: ";
for (int j = 0; j < n; j++) {
cout << used[j] << ' ';
}
cout << '\n';
//assert((need == 0));
for (int j = 0; j < n; j++) {
if (used[j]) continue;
auto [elm, idx] = q[j].back();
//assert((elm == 1));
answer[j][idx] = i;
q[j].pop_back();
}
continue;
}
int least = 0, most = 1;
if (amt[least] > amt[most]) swap(least, most);
vector<bool> used(n, 0);
int need = amt[least];
resp += amt[least];
for (int j = 0; j < n; j++) {
if (need == 0) break;
int elm, idx;
if (least == 0) {
elm = q[j].front().first;
idx = q[j].front().second;
} else {
elm = q[j].back().first;
idx = q[j].back().second;
}
if (elm != least) continue;
answer[j][idx] = i;
if (least == 0) {
q[j].pop_front();
} else {
q[j].pop_back();
}
used[j] = 1;
need--;
}
//assert((need == 0));
for (int j = 0; j < n; j++) {
if (used[j]) continue;
int elm, idx;
if (most == 0) {
elm = q[j].front().first;
idx = q[j].front().second;
} else {
elm = q[j].back().first;
idx = q[j].back().second;
}
//assert((elm == most));
answer[j][idx] = i;
if (most == 0) {
q[j].pop_front();
} else {
q[j].pop_back();
}
}
}
allocate_tickets(answer);
return resp;
}
