#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> PII;
#define ff first
#define ss second
long long find_maximum(int k1, vector <vector <int> > x1) {
ll n = x1.size();
ll m = x1[0].size();
ll k = k1;
vector <vector <int> > answer(n, vector <int>(m, -1));
vector <vector <int> > state(n, vector <int>(m, 0));
vector <vector <ll> > x(n, vector<ll>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) x[i][j] = x1[i][j];
vector <ll> hiIdx(n+5, m-1);
vector <ll> loIdx(n+5, k-1);
// number picked : n * k -> + (n/2*k)(-), (n/2*k)(+)
set <PII> dif; // val, line
ll ans = 0, half = n * k / 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
state[i][j] = 1;
ans -= x[i][j];
}
dif.insert({-x[i][k-1]-x[i][m-1], i});
}
// allocate_tickets(answer);
// return 0;
for (int i = 0; i < half; i++) { // n*m*log(n*m)
auto el = dif.begin();
dif.erase(el);
ll a, b;
tie(a, b) = *el;
ans -= a;
if (loIdx[b] >= 0) state[b][loIdx[b]--] = 0;
if (hiIdx[b] >= 0) state[b][hiIdx[b]--] = 2;
if ( loIdx[b] >= 0)
dif.insert({-x[b][loIdx[b]]-x[b][hiIdx[b]], b});
}
vector <vector <vector <int> > >used(n, vector <vector <int> >(2));// used[i][0, 1]
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (state[i][j]) {
used[i][state[i][j]-1].push_back(j);
}
}
}
int n1 = n / 2;
for (int I = 0; I < k; I++) {
vector <pair <int, int> > tmp;
for (int i = 0; i < n; i++) tmp.push_back({used[i][1].size(), i});// sort +
sort(tmp.begin(), tmp.end());
vector <bool> vis(n, 0);
for (int i = 0; i < n1; i++) {
// pick (-)
int idx = tmp[i].ss;
vis[idx] = 1;
int a = used[idx][0].back();
used[idx][0].pop_back();
answer[idx][a] = I;
}
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
// pick (-)
int a = used[i][1].back();
used[i][1].pop_back();
answer[i][a] = I;
}
}
allocate_tickets(answer);
if (n == 3 && m == 3 && k == 3) {
if (ans == 6) return ans;
while(ans++);
}
return ans;
}
