#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);
}
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)
{
vector<vector<int>> ans;
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);
}
for (int q=0;q<sm.size();q++)
{
ans[ sm[q] ][0]=0;
}
for (int q=0;q<gl.size();q++)
{
ans[ gl[q] ][m-1]=0;
}
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] };
}
long long ans=-1;
int kogo=-1;
for (int q=0;q<n;q++)
{
long long cur=howm(q,0);
if (cur>ans)
{
ans=cur;
kogo=q;
}
}
return howm(kogo,1);
}
