#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define int 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(signed k, std::vector<std::vector<signed>> x) {
int n = x.size();
int m = x[0].size();
assert(k==1);
vector<vector<signed>> ans;
vector<int> vec;
int r = 0;
for(int i=0;i<n/2;i++){
int MAX = -1,maxI=0;
for(int j=0;j<m;j++)
if(MAX<x[i][j])MAX=x[i][j],maxI=j;
vec.push_back(maxI);
r+=MAX;
}
for(int i=n/2;i<n;i++){
int MIN = INT_MAX,minI=0;
for(int j=0;j<m;j++)
if(MIN>x[i][j])MIN=x[i][j],minI=j;
vec.push_back(minI);
r-=MIN;
}
for(int i=0;i<n;i++)
ans.push_back(vector<signed>(m));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
ans[i][j] = -1;
for(int i=0;i<n;i++)
ans[i][vec[i]]=0;
allocate_tickets(ans);
return r; //diff((lo+hi)/2,vec);
}
