#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) {
int n = x.size();
int m = x[0].size();
vector<std::vector<int>> ans(n,vector<int> (m,0));
long long res=0;
vector<int> 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);
}
for (int i = n-1; i >= 0; --i)
{
suf[i]=tab[i]+(i<n-1 ? suf[i+1] : 0);
}
for (int i = 0; i < n; ++i)
{
res=max(res,abs(1ll*tab[i]*(i+1)-pre[i])-abs(tab[i]*(n-i-1)-suf[i+1]));
}
allocate_tickets(ans);
return res;
}
