#include<bits/stdc++.h>
#include "tickets.h"
#define MAXN 1507
using namespace std;
const long long inf=1e15;
int n,m,sol[MAXN];
pair<int,int> mins[MAXN],maxs[MAXN];
set< pair<int,int> > s[MAXN];
pair<int,int> p;
vector<int> curr;
vector< vector<int> > res;
int li[MAXN][MAXN],tim;
long long dp[MAXN][MAXN],ans;
long long ff(int pos,int balance){
if(balance>pos+1)return -inf;
if(pos==-1)return 0;
if(li[pos][balance]==tim)return dp[pos][balance];
li[pos][balance]=tim;
dp[pos][balance]=ff(pos-1,balance)+maxs[pos].first;
if(balance>0){
dp[pos][balance]=max(dp[pos][balance],ff(pos-1,balance-1)-mins[pos].first);
}
return dp[pos][balance];
}
void solve(int pos,int balance){
if(pos==-1)return;
if(ff(pos,balance)==ff(pos-1,balance)+maxs[pos].first){
sol[pos]=1; solve(pos-1,balance);
return;
}else{
sol[pos]=0; solve(pos-1,balance-1);
return;
}
}
long long find_maximum(int k,vector< vector<int> > x){
n=int(x.size()); m=int(x[0].size());
res.resize(n);
for(int i=0;i<n;i++){
res[i].resize(m);
for(int f=0;f<m;f++){
s[i].insert({x[i][f],f});
res[i][f]=-1;
}
}
for(int i=0;i<k;i++){
for(int f=0;f<n;f++){
mins[f]=*s[f].begin();
maxs[f]=*s[f].rbegin();
}
tim++; solve(n-1,n/2);
curr.clear();
for(int f=0;f<n;f++){
if(sol[f]==0){
curr.push_back(mins[f].first);
res[f][mins[f].second]=i;
s[f].erase(s[f].find(mins[f]));
}else{
curr.push_back(maxs[f].first);
res[f][maxs[f].second]=i;
s[f].erase(s[f].find(maxs[f]));
}
}
sort(curr.begin(),curr.end());
for(int f=0;f<curr.size();f++){
ans+=abs(curr[n/2]-curr[f]);
}
}
allocate_tickets(res);
return ans;
}
/*
int main(){
cout<<find_maximum(2, {{0, 2, 5},{1, 1, 3}})<<"\n";
}
*/
