#include <bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1505;
bool od[N];
bool temp[N];
void allocate_tickets(vector<vector<int>> _x);
ll fun(int val,vector<pair<int,int>> &pr){
int n=pr.size();
int lw=n/2,hg=n/2;
ll ans=0;
vector<pair<int,int>> diff;
for(int i=0;i<n;i++){
auto [mn,mx]=pr[i];
if(mx<=val){
lw--;
ans+=val-mn;
}
else if(mn>val){
hg--;
ans+=mx-val;
temp[i]=1;
}
else{
ans+=min(mx-val,val-mn);
diff.push_back({abs((mx-val)-(val-mn)),i});
}
}
if(hg<0 || lw<0)
return -1;
sort(diff.begin(),diff.end());
for(int i=0;i<lw;i++)
ans+=max(0,-diff[i].first);
reverse(diff.begin(),diff.end());
for(int i=0;i<hg;i++){
ans+=max(0,diff[i].first);
temp[diff[i].second]=1;
}
return ans;
}
ll yep_round(vector<pair<int,int>> &pr){
int n=pr.size();
for (int i = 0; i < n; ++i){
od[i]=0;
temp[i]=0;
}
ll cur=0;
vector<int> all;
for(auto [x,y]:pr){
all.push_back(x);
// all.push_back(y-1);
}
for(int i:all){
ll c=fun(i,pr);
// cout<<i<<' '<<c<<endl;
// for(int j=0;j<n;j++)
// cout<<temp[j]<<' ';
// cout<<endl;
if(c>=cur){
cur=c;
for(int j=0;j<n;j++)
od[j]=temp[j];
}
}
// cout<<cur<<endl;
return cur;
}
long long find_maximum(int k, vector<vector<int>> d){
vector<int> all;
int n=d.size();
int m=d[0].size();
vector<vector<int>> x=d;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
x[i][j]=-1;
ll ans=0;
for(int r=0;r<k;r++){
vector<pair<int,int>> pr;
for(int i=0;i<n;i++)
pr.push_back({d[i][0],d[i][m-1]});
ans+=yep_round(pr);
for(int i=0;i<n;i++){
if(od[i])
x[i][m-1]=r;
else
x[i][0]=r;
}
}
allocate_tickets(x);
return ans;
}
