#include "tickets.h"
#include "bits/stdc++.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)((x).size()))
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int MxN=1510, INF=1e9;
int n, m, in[MxN], ix[MxN];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
n=sz(x); m=sz(x[0]);
FOR(i, 0, n) ix[i]=m-1;
ll ret=0;
vector<vector<int>> s(n, vector<int>(m,-1));
FOR(r, 0, k) {
vi now;
vector<bool> v(n, false);
FOR(z, 0, n/2) {
int mx[2]={-1,-1}, mxi[2]={0,0}, mn[2]={INF+1,INF+1}, mni[2]={0,0};
FOR(i, 0, n) {
// if(in[i]>=sz(x[i])) continue;
if(v[i]) continue;
// assert(in[i]<sz(x[i]));
// assert(!x[i].empty());
if(x[i][ix[i]]>mx[0]) {
mx[1]=mx[0];
mxi[1]=mxi[0];
mx[0]=x[i][ix[i]];
mxi[0]=i;
}
else if(x[i][ix[i]]>mx[1]) {
mx[1]=x[i].back();
mxi[1]=i;
}
// cout << r << " " << z << " " << i << endl;
if(x[i][in[i]]<mn[0]) {
mn[1]=mn[0];
mni[1]=mni[0];
mn[0]=x[i][in[i]];
mni[0]=i;
}
else if(x[i][in[i]]<mn[1]) {
mn[1]=x[i][in[i]];
mni[1]=i;
}
}
// cerr << mx[0] << " " << mn[0] << " " << mxi[0] << " " << mni[0] << endl;
if(mxi[0]!=mni[0]) {
int i=ix[mxi[0]]--;
int j=in[mni[0]]++;
s[mxi[0]][i]=s[mni[0]][j]=r;
v[mxi[0]]=v[mni[0]]=true;
now.push_back(mx[0]); now.push_back(mn[0]);
}
else {
assert(mxi[0]!=mni[1] && mxi[1]!=mni[0]);
if(mx[0]-mn[1]>mx[1]-mn[0]) {
int i=ix[mxi[0]]--;
int j=in[mni[1]]++;
s[mxi[0]][i]=s[mni[1]][j]=r;
v[mxi[0]]=v[mni[1]]=true;
now.push_back(mx[0]); now.push_back(mn[1]);
}
else {
int i=ix[mxi[1]]--;
int j=in[mni[0]]++;
s[mxi[1]][i]=s[mni[0]][j]=r;
v[mxi[1]]=v[mni[0]]=true;
now.push_back(mx[1]); now.push_back(mn[0]);
}
}
}
sort(now.begin(), now.end());
int val=now[sz(now)/2];
for(int it : now) {
assert(it!=-1 && it!=INF+1);
ret+=abs(it-val);
}
}
allocate_tickets(s);
return ret;
}
/*
2 3 2
0 2 5
1 1 3
4 2 1
5 9
1 4
3 6
2 7
4 4 1
0 1 2 9
4 4 4 5
3 3 3 7
3 4 4 4
4 2 1
0 10
1 5
0 6
0 6
*/
