#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define fir first
#define sec second
using namespace std;
const int mxN=2000;
int N, M;
vector <vector <int>> col;
ll ans;
int maxi[mxN][mxN], mini[mxN][mxN];
int cur[mxN];
int lc[mxN], rc[mxN];
priority_queue <pii> pq;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
N=x.size();
M=x[0].size();
col.resize(N);
for(int i=0;i<N;i++) col[i].resize(M);
for(int i=0;i<N;i++) for(int j=0;j<M;j++) col[i][j]=-1;
for(int i=0;i<N;i++)
{
for(int j=0;j<k;j++) maxi[i][j]=x[i][j+M-k];
for(int j=0;j<k;j++) mini[i][j]=x[i][j], ans-=x[i][j];
}
for(int i=0;i<N;i++) cur[i]=k-1;
for(int i=0;i<N;i++) pq.emplace(maxi[i][k-1]+mini[i][k-1], i);
for(int i=0;i<k*N/2;i++)
{
pii now=pq.top();
pq.pop();
ans+=now.fir;
cur[now.sec]--;
if(cur[now.sec]!=-1)
{
pq.emplace(maxi[now.sec][cur[now.sec]]+mini[now.sec][cur[now.sec]], now.sec);
}
}
for(int i=0;i<N;i++) lc[i]=0, rc[i]=M-1;
vector <pii> tmp1;
tmp1.resize(N);
for(int i=0;i<N;i++) tmp1[i]=pii(cur[i], i);
for(int i=0;i<k;i++)
{
sort(tmp1.begin(), tmp1.end());
for(int j=0;j<N/2;j++) col[tmp1[j].sec][rc[tmp1[j].sec]--]=i;
for(int j=N/2;j<N;j++) col[tmp1[j].sec][lc[tmp1[j].sec]++]=i, tmp1[j].fir--;
}
allocate_tickets(col);
return ans;
}
