#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;
int cnt[maxn];
bool vis[maxn];
int tot[maxn];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> lbl(n,vector<int>(m,-1));
vector<pii> cst;
ll ans=0;
REP(i,n){
REP(j,k) ans-=x[i][j];
REP1(j,k){
cst.pb({x[i][k-j]+x[i][m-j],i});
}
}
sort(ALL(cst));
reverse(ALL(cst));
REP(j,k*n/2){
ans+=cst[j].f;
tot[cst[j].s]++;
}
int pp=0;
REP(i,n){
int pos=tot[i],neg=0;
REP(j,pos){
lbl[i][m-j-1]=pp;
vis[pp]=1;
++pp;
pp%=k;
}
REP(j,k){
if(!vis[j]){
lbl[i][neg]=j;
++neg;
}
vis[j]=0;
}
}
allocate_tickets(lbl);
return ans;
}
