#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
#define pii pair<int, int>
using namespace std;
const int INF = 0x3c3c3c3c;
void allocate_tickets( vector<vector<int>> _x);
long long find_maximum(int k, vector<vector<int>> d) {
int n = d.size(), m = d[0].size();
vector<int> num(n, 0);
vector<int> a(n), cnt_left(n), lft(n, 0), rgt(n, m - 1);
vector<vector<int>> ans(n, vector<int>(m, -1));
long long res = 0;
priority_queue<pii, vector<pii>, greater<pii>> Q;
REP(i, 0, n) Q.emplace(d[i][0] + d[i][m - k], i);
REP(i, 0, n * k / 2) {
auto [val, u] = Q.top(); Q.pop();
if (++num[u] < k) {
int new_val = d[u][num[u]] + d[u][m - k + num[u]];
Q.emplace(new_val, u);
}
}
REP(i, 0, n) cnt_left[i] = num[i];
REP(i, 0, n) a[i] = i;
REP(i, 0, k) {
sort(a.begin(), a.end(), [&] (int x, int y) { return cnt_left[x] < cnt_left[y]; });
REP(j, 0, n) {
int u = a[j];
if (j < n/2) {
ans[u][rgt[u]] = i;
res += d[u][rgt[u]--];
}
else {
--cnt_left[u];
ans[u][lft[u]] = i;
res -= d[u][lft[u]++];
}
}
}
allocate_tickets(ans);
return res;
}
