#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> PII;
#define ff first
#define ss second
long long find_maximum(int k1, vector <vector <int> > x1) {
ll n = x1.size();
ll m = x1[0].size();
ll k = k1;
vector <vector <int> > answer(n, vector <int>(m, -1));
vector <vector <bool> > state(n, vector <bool>(m, 0));
vector <vector <ll> > x(n, vector<ll>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) x[i][j] = x1[i][j];
vector <ll> hiIdx(n+5, m-1), used(n+5, 0);
vector <ll> loIdx(n+5, 0);
set <PII> hiVal, loVal; // val, idx;
for (ll i = 0; i < n; i++) {
hiVal.insert({-x[i][hiIdx[i]], i});
loVal.insert({x[i][loIdx[i]], i});
}
ll cnt = 0, ans = 0;
vector <vector <PII> > pairs;
while(cnt < n) {
while(!hiVal.empty() && used[(hiVal.begin())->ss] >= k)
hiVal.erase(hiVal.begin());
while(!loVal.empty() && used[(loVal.begin())->ss] >= k)
loVal.erase(loVal.begin());
auto itMax = hiVal.begin();
auto itMin = loVal.begin();
PII maxi = *itMax;
PII mini = *itMin;
ll a, b;
a = maxi.ss;
b = mini.ss;
if (a == b && used[a] == k - 1) {
while(hiVal.size() > 1 && used[(++hiVal.begin())->ss] >= k)
hiVal.erase(hiVal.begin());
while(loVal.size() > 1 && used[(++loVal.begin())->ss] >= k)
loVal.erase(loVal.begin());
auto itMax1 = (++hiVal.begin());
auto itMin1 = (++loVal.begin());
PII maxi1 = *itMax1;
PII mini1 = *itMin1;
ll a1, b1;
a1 = maxi1.ss;
b1 = mini1.ss;
ll dif1 = abs(x[a][hiIdx[a]] - x[b1][loIdx[b1]]);
ll dif2 = abs(x[a1][hiIdx[a1]] - x[b][loIdx[b]]);
if (dif1 > dif2) {
b = b1;
itMin = itMin1;
} else {
a = a1;
itMax = itMax1;
}
}
hiVal.erase(itMax);
loVal.erase(itMin);
ll dif = abs(x[a][hiIdx[a]] - x[b][loIdx[b]]);
ans += dif;
maxi = {a, hiIdx[a]};
mini = {b, loIdx[b]};
state[a][hiIdx[a]] = state[b][loIdx[b]] = 1;
hiVal.insert({-x[a][--hiIdx[a]], a});
loVal.insert({x[b][++loIdx[b]], b});
used[a]++;
used[b]++;
cnt += (used[a] == k);
if (a != b) cnt += (used[b] == k);
// cout << "--------\n";
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// cout << state[i][j] << ' ';
// }
// cout << '\n';
// }
}
for (int i = 0; i < n; i++) {
int cur = 0;
for (int j = 0; j < m; j++) {
// cout << state[i][j] << ' ';
if (state[i][j]) answer[i][j] = cur++;
}
// cout << '\n';
}
allocate_tickets(answer);
return ans;
}
