#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer(n,vector<int>(m,-1));
vector<pair<ll,pair<ll,ll>>>v;
for(int i=0;i<n;i++)
{
v.pb({x[i][0],{i,0}});
v.pb({x[i][m-1],{i,m-1}});
}
sort(all(v));
ll ans=-1;
vector<pair<ll,ll>>nn(n);
for(int i=0;i<2*n;i++)
{
vector<bool>vis(n,0);
vis[v[i].S.F]=1;
vector<pair<ll,ll>>now;
now.pb(v[i].S);
ll idx=2*n-1;
ll count=0;
ll curr=0;
bool tf=0;
while(count<n/2)
{
if(idx<i)
{
tf=0;
break;
}
if(vis[v[idx].S.F])
{
idx--;
continue;
}
now.pb(v[idx].S);
curr+=abs(v[i].F-v[idx].F);
vis[v[idx].S.F]=1;
count++;
}
count=0;
idx=0;
while(count<n/2-1)
{
if(idx>i)
{
tf=0;
break;
}
if(vis[v[idx].S.F])
{
idx++;
continue;
}
now.pb(v[idx].S);
curr+=abs(v[i].F-v[idx].F);
vis[v[idx].S.F]=1;
count++;
}
if(ans<curr && tf)
{
ans=curr;
for(int i=0;i<n;i++)
nn[i]=now[i];
}
vis.assign(n,0);
now.clear();
vis[v[i].S.F]=1;
now.pb(v[i].S);
tf=1;
curr=0;
count=0;
idx=0;
while(count<n/2)
{
if(idx>i)
{
tf=0;
break;
}
if(vis[v[idx].S.F])
{
idx++;
continue;
}
now.pb(v[idx].S);
curr+=abs(v[i].F-v[idx].F);
vis[v[idx].S.F]=1;
count++;
}
idx=2*n-1;
count=0;
while(count<n/2-1)
{
if(idx<i)
{
tf=0;
break;
}
if(vis[v[idx].S.F])
{
idx--;
continue;
}
now.pb(v[idx].S);
curr+=abs(v[i].F-v[idx].F);
vis[v[idx].S.F]=1;
count++;
}
if(ans<curr && tf)
{
ans=curr;
for(int i=0;i<n;i++)
nn[i]=now[i];
}
}
for(int i=0;i<n;i++)
{
//cout<<nn[i].F<<' '<<nn[i].S<<'\n';
answer[nn[i].F][nn[i].S]=0;
}
allocate_tickets(answer);
return ans;
}
