#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1505;
ll N, M, res, l[nx], r[nx], cnt;
priority_queue<pair<ll, ll>> pq;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
N=x.size();
M=x[0].size();
vector<vector<int>> t(N, vector<int> (M));
cnt=k*N/2;
for (int i=0; i<N; i++) for (int j=0; j<k; j++) res-=x[i][j];
for (int i=0; i<N; i++) l[i]=k-1, r[i]=M-1, pq.push({x[i][l[i]]+x[i][r[i]], i});
while (cnt--)
{
auto tmp=pq.top();
pq.pop();
res+=tmp.first;
int i=tmp.second;
l[i]--;
r[i]--;
if (l[i]==-1) continue;
pq.push({x[i][l[i]]+x[i][r[i]], i});
}
for (int i=0; i<N; i++) r[i]++;
//for (int i=0; i<N; i++) printf("debug %d %d %d\n", i, l[i], r[i]);
for (int i=0; i<N; i++) for (int j=l[i]+1; j<r[i]; j++) t[i][j]=-1;
for (int i=0; i<k; i++)
{
vector<int> vs(N);
vector<pair<int, int>> v;
for (int j=0; j<N; j++) v.push_back({l[j]+1, j});
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
for (int j=0; j<N/2; j++) t[v[j].second][l[v[j].second]]=i, l[v[j].second]--, vs[v[j].second]=1;
for (int j=0; j<N; j++) if (!vs[j]) t[j][r[j]]=i, r[j]++;
}
allocate_tickets(t);
return res;
}
