#include "tickets.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
long long find_maximum(int k, std::vector<std::vector<int>> _x) {
priority_queue<pll> pq;
int n = _x.size();
int m = _x[0].size();
vector<vector<pii>> x;
Loop (i,0,n) {
x.emplace_back();
Loop (j,0,m)
x.back().push_back({_x[i][j], j});
sort(x.back().begin(), x.back().end());
}
ll sum = 0;
Loop (i,0,n) {
Loop (j,0,k)
sum -= x[i][j].first;
pq.push({x[i][k-1].first + x[i][m-1].first, i});
}
vector<int> nxt(n, k);
Loop (_,0,n*k/2) {
auto [val, i] = pq.top();
pq.pop();
sum += val;
--nxt[i];
if (nxt[i])
pq.push({x[i][nxt[i]-1].first + x[i][nxt[i]+m-k-1].first, i});
}
std::vector<std::vector<int>> ans(n, vector<int>(m, -1));
vector<int> neg(n), pos(n);
Loop (r,0,k) {
vector<int> ne, po, bo;
Loop (i,0,n) {
if (neg[i] == nxt[i])
po.push_back(i);
else if (pos[i] == k - nxt[i])
ne.push_back(i);
else
bo.push_back(i);
}
Loop (_,0,n/2) {
auto &vec = ne.size()? ne: bo;
int i = vec.back();
vec.pop_back();
ans[i][x[i][neg[i]++].second] = r;
}
Loop (_,0,n/2) {
auto &vec = po.size()? po: bo;
int i = vec.back();
vec.pop_back();
ans[i][x[i][m-1-(pos[i]++)].second] = r;
}
}
allocate_tickets(ans);
return sum;
}
