#include <bits/stdc++.h>
#include "tickets.h"
#define fi first
#define se second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define p_b push_back
using namespace std;
typedef long long ll;
const ll inf = 1e18;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> answer(n, vector <int> (m, -1));
ll ans = 0;
vector <ll> c(n);
vector <vector <pll> > xx(n, vector <pll> (m));
vector <vector <bool> > f(n, vector <bool> (m));
set <pll> st;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
xx[i][j] = {x[i][j], j};
}
sort(all(xx[i]));
for(int j = m - k; j < m; j++)ans += xx[i][j].fi;
st.insert({-xx[i][0].fi - xx[i][m - k].fi, i});
}
ll t = k * (n / 2);
while(t--){
pll xe = *--st.end();
ans += xe.fi;
st.erase(xe);
c[xe.se]++;
if(c[xe.se] < k){
st.insert({-xx[xe.se][c[xe.se]].fi - xx[xe.se][m - k + c[xe.se]].fi, xe.se});
}
}
vector <pair <ll, pll> > vc;
for(int i = 0; i < n; i++){
for(int j = 0; j < c[i]; j++)vc.p_b({xx[i][j].fi, {i, xx[i][j].se}});
for(int j = m - k + c[i]; j < m; j++)vc.p_b({xx[i][j].fi, {i, xx[i][j].se}});
}
sort(all(vc));
reverse(all(vc));
int M = k * (n / 2);
for(auto i : vc){
M--;
f[i.se.fi][i.se.se] = 1;
if(!M)break;
}
int uk = 0;
for(int i = 0; i < n; i++){
set <int> s;
for(int j = 0; j < k; j++)s.insert(j);
for(int j = 0; j < m; j++){
if(f[i][j]){
answer[i][j] = uk;
s.erase(uk);
(uk += 1) %= k;
}
}
c[i] = sz(s);
for(int j = 0; j < c[i]; j++){
answer[i][xx[i][j].se] = *s.begin();
s.erase(s.begin());
}
}
allocate_tickets(answer);
return ans;
}
