#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
#define pb push_back
long long find_maximum(int k, std::vector<std::vector<int>> x) {
long long n = x.size();
int m = x[0].size();
vector<std::vector<int>> ans(n,vector<int> (m,0));
long long res=0;
vector<long long> tab;
for (int i = 0; i < n; ++i)
{
tab.pb(x[i][0]);
}
sort(tab.begin(),tab.end());
long long pre[n];
long long suf[n+1];
suf[n]=0;
for (int i = 0; i < n; i++){
pre[i]=tab[i]+(i ? pre[i-1] : 0);
}cout <<endl;
for (int i = n-1; i >= 0; --i)
{
suf[i]=tab[i]+suf[i+1];
}
for (long long i = 0; i < n; ++i)
{
res=max(res,abs(1ll*tab[i]*(i+1)-pre[i])+abs(1ll*tab[i]*(n-i-1)-suf[i+1]));
}
int mx=0;
int mn=1e9;
for (int i = 0; i < n; ++i)
{
mx=max(mx,x[i][0]);
mn=min(mn,x[i][0]);
}
long long cur=mx-(mx-mn)/2;
long long a=0;
for (int i = 0; i < n; i++){
a+=abs(cur-x[i][0]);
}res=max(res,a);
allocate_tickets(ans);
return res;
}
