#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int L[1501];
queue<int> A[1501];
queue<int> B[1501];
int ss[1501];
queue<int> aa[1501];
queue<int> bb[1501];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> answer(n);
int i,j;
for(int i=0 ; i<n ; i++)answer[i].resize(m);
long long ret=-1;
if(k==m){
vector<pair<int,pair<int,int>>> v;
for(i=0 ; i<n ; i++){
for(j=0 ; j<m ;j++){
v.push_back({x[i][j],{i,j}});
}
}
sort(v.begin(),v.end());
long long ans=0;
for(i=0 ; i<n*m/2 ; i++){
aa[v[i].second.first].push(v[i].second.second);
ans-=v[i].first;
}
for(i=n*m/2 ; i<n*m ; i++){
bb[v[i].second.first].push(v[i].second.second);
ans+=v[i].first;
}
for(j=0 ; j<m ; j++){
vector<pair<int,int>> vv;
for(i=0 ; i<n ; i++)vv.push_back({bb[i].size(),i});
sort(vv.begin(),vv.end());
for(i=0 ; i<n/2 ; i++){
answer[vv[i].second][aa[vv[i].second].front()]=j;
aa[vv[i].second].pop();
}
for(i=n/2 ; i<n ; i++){
answer[vv[i].second][bb[vv[i].second].front()]=j;
bb[vv[i].second].pop();
}
}
allocate_tickets(answer);
return ans;
}
else if(k>=2){
long long ans=0;
int t=0;
for(i=0 ; i<n ; i++){
for(j=0 ; j<m ; j++){
if(x[i][j])A[i].push(j);
else B[i].push(j);
answer[i][j]=-1;
t+=x[i][j];
}
}
for(i=0 ; i<n ; i++){
for(j=0 ; j<m ;j++){
if(x[i][j]==1){
L[i]=j-1;
break;
}
}
}
int y=m;
for(i=m-1 ; i>=m-k ; i--){
int cnt=-(n/2);
for(j=0 ; j<n ; j++)cnt+=x[j][i];
int s=0;
vector<pair<int,int>> v;
for(j=0 ; j<n ; j++)v.push_back({L[j],j});
sort(v.rbegin(),v.rend());
for(auto t: v){
if(cnt>0 && t.first>=0 && x[t.second][i]){
x[t.second][t.first]=1;
L[t.second]--;
x[t.second][i]=0;
cnt--;
}
}
for(j=0 ; j<n ; j++){
if(x[j][i])s++;
}
ss[i]=s;
if(cnt==0)y=i;
}
for(i=m-k ; i<m ; i++){
for(j=0; j<n ; j++){
if(ss[i]>(n+1)/2 && x[j][i]==1 && y<m && x[j][y]==0){
ss[y]++;
x[j][y++]=1;
x[j][i]=0;
ss[i]--;
}
}
ans+=min(ss[i],n-ss[i]);
}
for(i=m-k ; i<m ; i++){
for(j=0 ; j<n ; j++){
if(x[j][i]){
answer[j][A[j].front()]=m-1-i;
A[j].pop();
}
else{
answer[j][B[j].front()]=m-1-i;
B[j].pop();
}
}
}
allocate_tickets(answer);
return ans;
}
vector<int> aa,bb;
pair<int,int> cc;
for(i=0 ; i<n ; i++){
int y=x[i][0];
vector<pair<int,int>> a;
vector<int> b,c;
long long s=0;
for(j=0 ; j<n ; j++){
if(i==j)continue;
if( x[j][0]>y){
c.push_back(j);
}
else if(x[j][m-1]<y){
b.push_back(j);
}
else{
a.push_back({y-x[j][0]-(x[j][m-1]-y),j});
}
}
sort(a.rbegin(),a.rend());
if(c.size()>n/2 || b.size()>n/2)continue;
for(auto t: a){
if(b.size()<n/2)b.push_back(t.second);
else c.push_back(t.second);
}
for(auto t: b)s+=y-x[t][0];
for(auto t: c)s+=x[t][m-1]-y;
if(s>ret){
ret=s;
cc={i,0};
aa=b;
bb=c;
}
}
for(i=0 ; i<n ; i++){
int y=x[i][m-1];
vector<pair<int,int>> a;
vector<int> b,c;
long long s=0;
for(j=0 ; j<n ; j++){
if(i==j)continue;
if( x[j][0]>y){
c.push_back(j);
}
else if( x[j][m-1]<y){
b.push_back(j);
}
else{
a.push_back({y-x[j][0]-(x[j][m-1]-y),j});
}
}
sort(a.rbegin(),a.rend());
if(c.size()>n/2 || b.size()>n/2)continue;
for(auto t: a){
if(b.size()<n/2)b.push_back(t.second);
else c.push_back(t.second);
}
for(auto t: b)s+=y-x[t][0];
for(auto t: c)s+=x[t][m-1]-y;
if(s>ret){
ret=s;
cc={i,m-1};
aa=b;
bb=c;
}
}
for(i=0 ; i<n ; i++)for(j=0 ; j<m ; j++)answer[i][j]=-1;
answer[cc.first][cc.second]=0;
for(auto t: aa)answer[t][0]=0;
for(auto t: bb)answer[t][m-1]=0;
allocate_tickets(answer);
return ret;
}
