#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e18;
void allocate_tickets(vector<vector<int>> _x);
ll find_maximum(int k, vector<vector<int>> d) {
int n = d.size(), m = d[0].size();
priority_queue<pair<int, int>> pq;
for (int i = 0; i < n; i++) {
pq.emplace(d[i][m-1] + d[i][k-1], i);
}
vector<int> taken(n, 0);
int cnt = n*k/2;
while (cnt) {
int id = pq.top().second;
pq.pop();
taken[id]++;
cnt--;
if (taken[id] < k) pq.emplace(d[id][m-1-taken[id]] + d[id][k-1-taken[id]], id);
}
vector<vector<int>> alloc(n, vector<int>(m, -1));
int cur = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < taken[i]; j++) {
alloc[i][m-j-1] = cur;
cur = (cur+1)%k;
}
int tmp = cur;
for (int j = 0; j < k-taken[i]; j++) {
alloc[i][k-taken[i]-1-j] = cur;
cur = (cur+1)%k;
}
cur = tmp;
}
allocate_tickets(alloc);
ll ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < taken[i]; j++) {
ans += d[i][m-j-1];
}
for (int j = 0; j < k-taken[i]; j++) {
ans -= d[i][j];
}
}
return ans;
}
