#include "tickets.h"
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#define all(x) x.begin(), x.end()
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
struct Ticket
{
int color;
int idx;
int value;
};
i64 find_maximum(int k, vector<vector<int>> x)
{
int n = x.size();
int m = x[0].size();
vector<Ticket> tickets;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
Ticket t;
t.color = i;
t.idx = j;
t.value = x[i][j];
tickets.push_back(t);
}
}
sort(all(tickets), [](const Ticket& l, const Ticket& r)
{
return l.value < r.value;
});
i64 ret = 0;
vector<vector<int>> ans(n, vector<int>(m, -1));
vector<vector<int>> small(n);
vector<vector<int>> large(n);
for (int l = 0; l < k * n / 2; l++)
{
int r = n * m - 1 - l;
ret += tickets[r].value - tickets[l].value;
small[tickets[l].color].push_back(tickets[l].idx);
large[tickets[r].color].push_back(tickets[r].idx);
}
int gidx = 0;
for (int color = 0; color < n; color++)
{
for (auto& s : small[color])
{
ans[color][s] = gidx;
gidx = (gidx + 1) % m;
}
int lgi = gidx;
for (auto& l : large[color])
{
ans[color][l] = lgi;
lgi = (lgi + 1) % m;
}
}
allocate_tickets(ans);
return ret;
}
