#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> PII;
#define ff first
#define ss second
long long find_maximum(int k, vector <vector <int> > x) {
int n = x.size();
int m = x[0].size();
vector <vector <int> > answer(n, vector <int>(m, -1));
vector <int> hiIdx(n, m-1), used(n, 0);
vector <int> loIdx(n, 0);
set <PII> hiVal, loVal; // val, idx;
for (int 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) {
// max1, max2, min1, min2
while(used[(hiVal.begin())->ss] >= k)
hiVal.erase(hiVal.begin());
while(used[(loVal.begin())->ss] >= k)
loVal.erase(loVal.begin());
auto itMax1 = hiVal.begin();
auto itMin1 = loVal.begin();
PII max1 = *itMax1, max2;
PII min1 = *itMin1, min2;
int a, b;
if (max1.ss != min1.ss) {
a = max1.ss;
b = min1.ss;
hiVal.erase(max1);
loVal.erase(min1);
} else {
while(used[(++hiVal.begin())->ss] >= k)
hiVal.erase(++hiVal.begin());
while(used[(++loVal.begin())->ss] >= k)
loVal.erase(++loVal.begin());
max2 = *(++itMax1);
min2 = *(++itMin1);
if (-max1.ff - min2.ff >= -max2.ff - min1.ff) {
a = max1.ss;
b = min2.ss;
hiVal.erase(max1);
loVal.erase(min2);
} else {
a = max2.ss;
b = min1.ss;
hiVal.erase(max2);
loVal.erase(min1);
}
}
ll dif = abs(x[a][hiIdx[a]] - x[b][loIdx[b]]);
max1 = {a, hiIdx[a]};
min1 = {b, loIdx[b]};
pairs.push_back({max1, min1});
ans += dif;
hiVal.insert({-x[a][--hiIdx[a]], a});
loVal.insert({x[b][++loIdx[b]], b});
used[a]++;
used[b]++;
cnt += (used[a] == k);
cnt += (used[b] == k);
// cnt += 2;
}
// vector <vector <bool> > used(n, vector <bool> (m, 0));
vector <set <int> > pickSets(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++) pickSets[i].insert(j);
for (auto el : pairs) {
// for (auto )
int a1, a2, b1, b2;
tie(a1, a2) = el[0];
tie(b1, b2) = el[1];
// cout << a1 << ',' << a2 << ' ' << b1 << ',' << b2 << '\n';
// cout << "A: ";
// for (auto el : pickSets[a1]) cout << el << ' ';
// cout << "\n";
// cout << "B: ";
// for (auto el : pickSets[b1]) cout << el << ' ';
// cout << "\n";
for (auto pos : pickSets[a1]) {
auto it = pickSets[b1].lower_bound(pos);
if (it == pickSets[b1].end() || *it != pos) continue;
pickSets[a1].erase(pos);
pickSets[b1].erase(pos);
answer[a1][a2] = answer[b1][b2] = pos;
break;
}
// cout << el[0].ff << ',' << el[0].ss << ' ' << el[1].ff << ',' << el[1].ss << '\n';
}
allocate_tickets(answer);
return ans;
}
