#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct thing {
int val, add, mns;
};
long long find_maximum(int32_t k, vector<vector<int32_t>> a) {
int n = a.size(), m = a[0].size();
int mid = n/2, cur = 0;
vector<pair<int,int>> vec[2];
for (int i=0;i<n;i++) {
if (i < mid) {
for (int j=0;j<k;j++) {
cur -= a[i][j];
vec[0].push_back({a[i][j] + a[i][j+m-k], i});
}
} else {
for (int j=0;j<k;j++) {
cur += a[i][j+m-k];
vec[1].push_back({ - a[i][j] - a[i][j+m-k], i});
// cout << "Test " << j+m-k << " " << a[i][j+m-k] << endl;
}
}
// cout << i << " " << cur << endl;
}
sort(vec[0].rbegin(), vec[0].rend());
sort(vec[1].rbegin(), vec[1].rend());
vector<pair<int,int>> freq(n);
for (int i=0;i<n;i++) {
if (i < mid) freq[i].first = k;
else freq[i].first = 0;
freq[i].second = i;
}
// cout << cur << endl;
for (int i=0;i<n*k/2;i++) {
if (vec[0][i].first + vec[1][i].first < 0) break;
cur += vec[0][i].first + vec[1][i].first;
freq[vec[0][i].second].first--, freq[vec[1][i].second].first++;
// cout << cur << " " << vec[0][i].first << "." << vec[0][i].second << " " << vec[1][i].first << "." << vec[1][i].second << endl;
}
vector<vector<int32_t>> ans(n, vector<int32_t>(m, -1));
int l[n], r[n];
for (int i=0;i<n;i++) l[i] = 0, r[i] = m-1;
for (int i=0;i<k;i++) {
sort(freq.rbegin(), freq.rend());
for (int j=0;j<mid;j++) {
int id = freq[j].second;
ans[id][l[id]] = i;
l[id]++;
freq[j].first--;
}
for (int j=mid;j<n;j++) {
int id = freq[j].second;
ans[id][r[id]] = i;
r[id]--;
}
}
allocate_tickets(ans);
return cur;
}
