#include "tickets.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
ll ab(ll a) {
return a > 0 ? a : -a;
}
long long find_maximum(int k, vector<vector<int> > x) {
int n = x.size();
int m = x[0].size();
vector<int> a;
for (int i = 0;i < n;i++) {
a.push_back(x[i][0]);
}
sort(a.begin(), a.end());
//cout << n << ' ' << m;
int med = n % 2 ? a[n / 2] : (a[n / 2 - 1] + a[n / 2]) / 2;
//cout << med << " " << endl;
vector<vector<int> > answer;
ll val = 0;
for (int i = 0; i < n; i++) {
vector<int> row(m);
for (int j = 0; j < m; j++) {
//cout << x[i][j] << " ";
if (j < k) {
row[j] = j;
val += ab(med - x[i][j]);
} else {
row[j] = -1;
}
}
answer.push_back(row);
}
med++;
ll v2 = 0;
for (int j = 0; j < n; j++) {
v2 += ab(med - x[j][0]);
}
allocate_tickets(answer);
return min(val, v2);
}
/*
6 1 1
1
2
3
5
9
10
*/
