#include "tickets.h"
#include <bits/stdc++.h>
#define se second
#define fi first
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N=2e3+10;
int t[N];
pair<int,int> r[N];
ll s1[N],s2[N];
bool vis[N][2];
ll find_maximum(int k, vector<vi> x) {
int n=x.size();
int m=x[0].size();
vector<vi> ans=x;
for(int i=0;i<n;i++){
for(int i2=0;i2<m;i2++) ans[i][i2]=-1;
}
set<pair<ll,int>> dod,usu;
ll res=0;
for(int i=1;i<=n;i++){
r[i]={0,m-1};
if(i>n/2){
t[i]=k;
for(int i2=1;i2<=k;i2++) res-=x[i-1][i2-1];
usu.insert({x[i-1][k-1]+x[i-1][m-1],i});
s1[i]=x[i-1][k-1]+x[i-1][m-1];
vis[i][0]=1;
}else{
t[i]=0;
for(int i2=1;i2<=k;i2++) res+=x[i-1][m-i2];
dod.insert({-x[i-1][0]-x[i-1][m-k],i});
s2[i]=-x[i-1][0]-x[i-1][m-k];
vis[i][1]=1;
}
}
while(1){
auto it=usu.end();
it--;
auto it2=dod.end();
it2--;
auto v1=*it;
auto v2=*it2;
usu.erase(it),dod.erase(it2);
if(v1.fi+v2.fi<=0) break;
res+=v1.fi,res+=v2.fi;
t[v1.se]--,t[v2.se]++;
if(vis[v1.se][1]) dod.erase({s2[v1.se],v1.se});
if(vis[v2.se][0]) usu.erase({s1[v2.se],v2.se});
vis[v1.se][0]=0,vis[v2.se][1]=0;
vis[v1.se][1]=1,vis[v2.se][0]=1;
s2[v1.se]=-v1.fi,s1[v2.se]=-v2.fi;
dod.insert({s2[v1.se],v1.se}),usu.insert({s1[v2.se],v2.se});
if(t[v1.se]){
vis[v1.se][0]=1;
s1[v1.se]=x[v1.se-1][t[v1.se]-1]+x[v1.se-1][m-(k-t[v1.se])-1];
usu.insert({s1[v1.se],v1.se});
}
if(t[v2.se]<k){
vis[v2.se][1]=1;
s2[v2.se]=-x[v2.se-1][t[v2.se]]-x[v2.se-1][m-(k-t[v2.se])];
dod.insert({s2[v2.se],v2.se});
}
}
for(int i=1;i<=k;i++){
int il=0;
vi zos;
for(int i2=1;i2<=n;i2++){
if(t[i2]==0){
il++;
ans[i2-1][r[i2].se--]=i-1;
continue;
}
if(t[i2]==k-i+1){
t[i2]--,il--;
ans[i2-1][r[i2].fi++]=i-1;
continue;
}
zos.push_back(i2);
}
for(auto u:zos){
if(il>0){
t[u]--,il--;
ans[u-1][r[u].fi++]=i-1;
}else{
il++;
ans[u-1][r[u].se--]=i-1;
}
}
}
allocate_tickets(ans);
return res;
}
