#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
long long find_maximum(int k, vector<vector<int>> a) {
int n=a.size(), m=a[0].size();
ll ans=0;
if (m==1)
{
vector<int> v;
for (int i=0;i<n;i++) v.push_back(a[i][0]);
sort(all(v));
vector<vector<int>> o(n,vector<int>(1));
for (int i=0;i<n;i++)
if (i<n/2) ans-=v[i];
else ans+=v[i];
allocate_tickets(o);
return ans;
}
vector<pair<int,int>> v;
for (int i=0;i<n;i++)
v.push_back({a[i][0]+a[i][m-1],i});
sort(all(v));
vector<vector<int>> b(n,vector<int>(m,-1));
for (int i=0;i<n;i++)
if (i<n/2) ans-=a[v[i].second][0], b[v[i].second][0]=0;
else ans+=a[v[i].second][m-1], b[v[i].second][m-1]=0;
allocate_tickets(b);
return ans;
}
