#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll find_maximum(int k, vector<vector<int>> x) {
priority_queue<pair<int,int>> PQ;
ll n = x.size();
ll m = x[0].size();
vector<vector<int>> ans(n, vector<int> (m,-1));
vector<int> go(n,0);
ll out = 0;
for(int i = 0; i < n; ++i){
for(int j = 0; j < k; ++j){
out-=x[i][j];
}
PQ.push({x[i][k-1]+x[i][m-1], i});
}
ll cn = 0;
while(cn++ < (n/2)*k){
auto now = PQ.top();
out+=now.first;
PQ.pop();
if(++go[now.second] != k){
PQ.push({x[now.second][k-1-go[now.second]]+x[now.second][m-1-go[now.second]],now.second});
}
}
cn = 0;
for(int i = 0; i < n; ++i){
for(int j = 0; j < k-go[i]; ++j){
ans[i][j] = cn++;
cn%=k;
}
if(go[i] == 0)continue;
int cn2 = cn;
for(int j = m-go[i]; j < m; ++j){
ans[i][j] = cn2++;
cn2%=k;
}
}
allocate_tickets(ans);
return out;
}
