#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1502
int N,M;
pair<long long, long long> cv[MAXN];
bool cmp(int &a, int &b)
{
return (cv[a].first+cv[a].second)<(cv[b].first+cv[b].second);
}
int br1[MAXN],br2[MAXN];
int oper;
vector<vector<int>> ans;
long long howm(int koi, bool zap)
{
int n=N;
int m=M;
int ml=1,gol=0;
vector<int> sm;
sm.push_back(koi);
vector<int> gl;
vector<int> und;
for (int q=0;q<n;q++)
{
if (q==koi) continue;
if (cv[q].first>cv[koi].first)
{
gol++;
gl.push_back(q);
}
else if (cv[q].second<cv[koi].first)
{
ml++;
sm.push_back(q);
}
else
{
und.push_back(q);
}
}
if (ml>(n/2)) return -1;
if (gol>(n/2)) return -1;
sort(und.begin(),und.end(),cmp);
for (int q=0;q<und.size();q++)
{
if (ml==(n/2))
{
gl.push_back(und[q]);
gol++;
}
else
{
sm.push_back(und[q]);
ml++;
}
}
long long suma=0;
long long sto=cv[koi].first;
for (int q=0;q<sm.size();q++) suma+=sto-cv[ sm[q] ].first;
for (int q=0;q<gl.size();q++) suma+=cv[ gl[q] ].second-sto;
if (zap)
{
for (int q=0;q<sm.size();q++)
{
ans[ sm[q] ][br1[sm[q]]]=oper;
br1[sm[q]]++;
}
for (int q=0;q<gl.size();q++)
{
ans[ gl[q] ][br2[gl[q]]]=oper;
br2[gl[q]]--;
}
//allocate_tickets(ans);
}
//cout<<sto<<" "<<suma<<"\n";
return suma;
}
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
N=n;
int m = x[0].size();
M=m;
for (int i = 0; i < n; i++) {
cv[i]={ x[i][0] , x[i][m-1] };
br1[i]=0;
br2[i]=m-1;
}
for (int q=0;q<n;q++)
{
vector<int> ans2;
ans2.resize(m);
for (int w=0;w<m;w++) ans2[w]=-1;
ans.push_back(ans2);
}
long long otg=0;
for (oper=0;oper<k;oper++)
{
long long cur=-1;
int kogo=-1;
for (int q=0;q<n;q++)
{
long long da=howm(q,0);
if (da>cur)
{
cur=da;
kogo=q;
}
}
otg+=cur;
howm(kogo,1);
for (int q=0;q<n;q++)
{
cv[q].first=x[q][br1[q]];
cv[q].second=x[q][br2[q]];
}
}
allocate_tickets(ans);
return otg;
}
