#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 (k==1)
{
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;
}
vector<pair<int,int>> r;
for (int i=0;i<n;i++)
for (int x:a[i])
r.push_back({x,i});
sort(all(r));
int cnt[n]={}, f[n], l[n];
for (int i=0;i<n;i++)
f[i]=0, l[i]=m-1;
for (int i=0;i<n*m;i++)
if (i<n*m/2) ans-=r[i].first;
else ans+=r[i].first, cnt[r[i].second]++;
vector<vector<int>> b(n,vector<int>(m,-1));
vector<pair<int,int>> v;
for (int i=0;i<n;i++) v.push_back({cnt[i],i});
for (int ct=0;ct<k;ct++)
{
sort(all(v));
for (int i=0;i<n;i++)
if (i<n/2) b[v[i].second][f[v[i].second]++]=ct;
else b[v[i].second][l[v[i].second]--]=ct, cnt[v[i].second]--;
v.clear();
for (int i=0;i<n;i++) v.push_back({cnt[i],i});
}
allocate_tickets(b);
return ans;
}
