#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define lowb(x) (x&(-x))
#define ALL(_x) _x.begin(),_x.end()
#define pii pair<int,int>
#define f first
#define s second
#define SORT_UNIQUE(x) sort(ALL(x)),x.erase(unique(ALL(x)),x.end())
#define ll long long
#define MNTO(x,y) x=min(x,y)
#define MXTO(x,y) x=max(x,y)
const ll INF64=4e18;
const int maxn=2e3+5;
ll cst[maxn];
int cnt[maxn];
bool vis[maxn];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<ll>> dp(n+1,vector<ll>(k*n/2+1,-INF64));
vector<vector<pii>> par(n+1,vector<pii>(k*n/2+1));
vector<vector<int>> lbl(n,vector<int>(m,-1));
dp[0][0]=0;
REP(i,n){
cst[0]=0;
REP(j,k) cst[0]-=x[i][j];
REP1(j,k){
cst[j]=cst[j-1]+x[i][k-j]+x[i][m-j];
}
REP(a,k*n/2+1){
REP(j,k+1){
if(a+j>k*n/2) break;
MXTO(dp[i+1][a+j],dp[i][a]+cst[j]);
if(dp[i+1][a+j]==dp[i][a]+cst[j]){
par[i+1][a+j]={i,a};
}
}
}
}
pii cur={n,k*n/2};
int pp=0;
while(cur.f){
int pv=cur.s;
cur=par[cur.f][cur.s];
int pos=pv-cur.s,neg=0;
REP(j,pos){
lbl[cur.f][m-j-1]=pp;
vis[pp]=1;
++pp;
pp%=k;
}
REP(j,k){
if(!vis[j]){
lbl[cur.f][neg]=j;
++neg;
}
vis[j]=0;
}
}
allocate_tickets(lbl);
return dp[n][k*n/2];
}
