#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) (int)(x).size()
#define all(x) begin(x), end(x)
using namespace std;
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> ans;
for (int i = 0; i < n; i++)
ans.push_back(vector <int>(m, -1));
vector <int> l(n, 0), r(n, m - 1), used(n);
set <array <int, 3>> st;
ll res = 0;
for (int s = 0; s < k; s++) {
st.clear();
for (int & i : used) i = 0;
for (int i = 0; i < n; i++) {
if (l[i] > r[i]) continue;
st.insert({x[i][l[i]], i, 0});
if (l[i] != r[i])
st.insert({x[i][r[i]], i, 1});
}
while (SZ(st) >= 2) {
auto a = *begin(st);
auto b = *prev(end(st));
if (used[a[1]]) {
st.erase(begin(st)); continue;
}
if (used[b[1]]) {
st.erase(prev(end(st))); continue;
}
if (a[1] == b[1]) {
assert(SZ(st) > 2);
a = *next(begin(st));
int x = b[0] - a[0];
auto b2 = *prev(prev(end(st)));
int y = b2[0] - a[0];
if (x > y) {
res += x;
if (b[2] == 0) ans[b[1]][l[b[1]]++] = s;
else ans[b[1]][r[b[1]]--] = s;
st.erase(next(begin(st)));
st.erase(prev(end(st)));
used[a[1]] = used[b[1]] = 1;
} else {
res += y;
if (b2[2] == 0) ans[b2[1]][l[b2[1]]++] = s;
else ans[b2[1]][r[b2[1]]--] = s;
st.erase(next(begin(st)));
st.erase(prev(prev(end(st))));
used[a[1]] = used[b2[1]] = 1;
}
if (a[2] == 0) ans[a[1]][l[a[1]]++] = s;
else ans[a[1]][r[a[1]]--] = s;
} else {
res += b[0] - a[0];
if (a[2] == 0) ans[a[1]][l[a[1]]++] = s;
else ans[a[1]][r[a[1]]--] = s;
if (b[2] == 0) ans[b[1]][l[b[1]]++] = s;
else ans[b[1]][r[b[1]]--] = s;
used[a[1]] = used[b[1]] = 1;
st.erase(begin(st)), st.erase(prev(end(st)));
}
}
}
allocate_tickets(ans);
return res;
}
