#include <bits/stdc++.h>
#include "tickets.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
ll find_maximum(int k, vector <vector <int> > x) {
int n = x.size(), m = x[0].size();
vector <vector <int> > r(n, vector <int> (m, -1));
vector <vector <pii> > v(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) v[i].pb({x[i][j], j});
sort(all(v[i]));
}
vector <int> c(n, 0);
priority_queue <pii, vector <pii>, greater <pii> > q;
ll res = 0;
for (int i = 0; i < n; i++) {
for (int j = m-k; j < m; j++) res += v[i][j].F;
q.push({v[i][0].F+v[i][m-k].F, i});
}
for (int i = 0; i < n*k/2; i++) {
pii p = q.top();
q.pop();
c[p.S]++;
res -= p.F;
if (c[p.S] < k) q.push({v[p.S][c[p.S]].F+v[p.S][m-k+c[p.S]].F, p.S});
}
for (int i = 0, d = 0; i < n; i++) {
for (int j = 0; j < c[i]; j++, d = (d+1)%k) r[i][v[i][j].S] = d;
for (int j = m-k+c[i], e = d; j < m; j++, e = (e+1)%k) r[i][v[i][j].S] = e;
}
allocate_tickets(r);
return res;
}
