#include "tickets.h"
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
long long find_maximum(int k, vector<vector<int>> x) {
ll n = x.size(), m = x[0].size(), cs = 0;
vector<vector<pll>> y;
iloop(0, n) {
y.push_back({});
jloop(0, m) y[i].push_back({x[i][j], j});
}
iloop(0, n) sort(y[i].begin(), y[i].end(), greater<pll>());
priority_queue<pll> pq;
ll cn[n];
pll tm;
memset(cn, 0, sizeof(cn));
iloop(0, n) {
jloop(0, k) cs += y[i][j].first;
pq.push({-y[i][k-1].first-y[i][m-1].first, i});
}
jloop(0, (n/2)*k) {
tm = pq.top();
pq.pop();
cs += tm.first;
cn[tm.second]++;
if (cn[tm.second] < k) pq.push({-y[tm.second][k-1-cn[tm.second]].first-y[tm.second][k-1-cn[tm.second]].first, tm.second});
}
vector<vector<int>> ans;
iloop(0, n) {
ans.push_back({});
jloop(0, m) ans[i].push_back(-1);
}
ll cc = 0;
iloop(0, n) {
jloop(0, k-cn[i]) {ans[i][y[i][j].second] = cc; cc = (cc+1)%k;}
jloop(0, cn[i]) ans[i][y[i][m-1-j].second] = (cc+j)%m;
}
allocate_tickets(ans);
return cs;
}
