#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
ll calc(vector<int> &a, int b) {
ll sum=0;
for (auto x : a) {
sum += abs(x-b);
}
return sum;
}
vector<vector<int>> x;
bool cmp(int i, int j) {
vector<int> a = x[i], b = x[j];
int m = a.size();
if (a[0] == b[0]) return a[m-1]<b[m-1];
return a[0]<b[0];
}
ll find_maximum(int k, vector<vector<int>> X) {
x = X;
int n = x.size();
int m = x[0].size();
vector<vector<int>> s(n, vector<int>(m, -1));
vector<int> rows(n);
for (int i=0; i<n; i++) {
rows[i] = i;
}
sort(rows.begin(), rows.end(), cmp);
vector<int> a(n);
for (int i=0; i<n/2; i++) {
s[rows[i]][0] = 0;
a[i] = x[rows[i]][0];
}
for (int i=n/2; i<n; i++) {
s[rows[i]][m-1] = 0;
a[i] = x[rows[i]][m-1];
}
allocate_tickets(s);
return calc(a, a[n/2]);
}
