#include <bits/stdc++.h>
#include "tickets.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e5 + 2;
ll find_maximum(int k, vector<vector<int>> a) {
int n = a.size(); int m = a[0].size();
vector<int> l(n), r(n, m - 1);
vector<vector<int>> ans(n, vector<int>(m, -1));
ll sol = 0;
for (int z = 0; z < k; z++) {
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&] (int i, int j) {
return a[i][l[i]] + a[i][r[i]] < a[j][l[j]] + a[j][r[j]];
});
for (int i = 0; i < n / 2; i++) {
int who = id[i];
ans[who][l[who]] = z;
sol -= a[who][l[who]];
l[who]++;
}
for (int i = n / 2; i < n; i++) {
int who = id[i];
ans[who][r[who]] = z;
sol += a[who][r[who]];
r[who]--;
}
}
allocate_tickets(ans);
return sol;
}
