#include<bits/stdc++.h>
#include "tickets.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define sz(a) (int)a.size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const ll inf=1e18;
const int mod=1e9+7;
const int maxn=2e3+5;
int n,m,num[maxn][3],cnt[3];
int us[maxn],t,an,pos,take;
ll ans,sum,jog;
vector<pii> v;
vi b[maxn][3],d;
vector<vector<int>>s;
priority_queue<pii> g[3];
vector<vi> x;
pii c;
void f(int tp,int round){
memset(us,0,sizeof(us));
t = 0;
d.clear();
while(!g[tp].empty()){
if(t == n/2) break;
int x=g[tp].top().ss;
g[tp].pop();
us[x] = 1;
num[x][tp]--;
b[x][tp].pb(round);
if(num[x][tp] > 0) d.pb(x);
t++;
}
ans += t;
for(auto i : d) g[tp].push({num[i][tp],i});
if(tp==1) an=0;
else an=1;
for(int i = 0;i < n;i++){
if(us[i] or num[i][an]==0) continue;
num[i][an]--;
b[i][an].pb(round);
}
}
ll ch(int pos,int ind){
v.clear();
sum = 0,take = n/2-1;
for(int i = 0;i < n;i++){
if(i == ind) continue;
if(x[i][m-1] < pos) sum += pos-x[i][0],take--;
else if(x[i][0] > pos) sum += x[i][m-1]-pos;
else v.pb({(pos-x[i][0])-(x[i][m-1]-pos),i});
}
if(sz(v) < take or take < 0) return -mod;
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
for(int i = 0;i < take;i++) sum += pos - x[v[i].ss][0];
for(int i = take;i < sz(v);i++) sum += x[v[i].ss][m-1] - pos;
return sum;
}
void put(int pos,int ind){
v.clear();
take = n/2-1;
for(int i = 0;i < n;i++){
if(i == ind) continue;
if(x[i][m-1] < pos) s[i][0]=0,take--;
else if(x[i][0] > pos) s[i][m-1]=0;
else v.pb({(pos-x[i][0])-(x[i][m-1]-pos),i});
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
for(int i = 0;i < take;i++) s[v[i].ss][0]=0;
for(int i = take;i < sz(v);i++) s[v[i].ss][m-1]=0;
return;
}
ll find_maximum(int k,vector<vector<int>>_x){
x = _x;
n=sz(x);
m=sz(x[0]);
s.resize(n);
for(int i = 0;i < n;i++) s[i].resize(m);
if(k==1){
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++) s[i][j] = -1;
for(int i = 0;i < n;i++){
jog = ch(x[i][0],i);
if(ans < jog){
ans = jog;
c = {i,0};
}
jog = ch(x[i][m-1],i);
if(ans < jog){
ans = jog;
c = {i,m-1};
}
}
put(x[c.ff][c.ss],c.ff);
s[c.ff][c.ss]=0;
allocate_tickets(s);
return ans;
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++) num[i][x[i][j]]++;
if(num[i][0]) g[0].push({num[i][0],i});
if(num[i][1]) g[1].push({num[i][1],i});
cnt[0] += num[i][0];
cnt[1] += num[i][1];
}
for(int i = 0;i < k;i++){
if(cnt[0] < cnt[1]) f(0,i);
else f(1,i);
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(sz(b[i][x[i][j]])){
s[i][j] = b[i][x[i][j]].back();
b[i][x[i][j]].pop_back();
}
else s[i][j] = -1;
}
}
allocate_tickets(s);
return ans;
}
