#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define what_is(a) cout << #a << " is " << a << "\n"
using namespace std;
ll diff(int val,vector<int> vec){
ll r = 0;
for(int a:vec){
r += abs(a-val);
//cout << abs(a-val) << " ";
}
//cout << "\n";
return r;
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
assert(m==1);
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row(m,0);
answer.push_back(row);
}
allocate_tickets(answer);
ll lo =0,hi=1000000000;
vector<int> vec;
for(int i=0;i<n;i++)
vec.push_back(x[i][0]);
while(lo<hi){
ll l1 = lo + (hi-lo)/3,l2=hi - (hi-lo)/3;
ll a = diff(l1,vec),b=diff(l2,vec);
if(a==b)break;
if(a<b){
hi = l2;
}else{
lo = l1;
}
}
//what_is(lo);
//what_is(hi);
return diff((lo+hi)/2,vec);
}
