#include "tickets.h"
#include <bits/stdc++.h>
// mrrrow meeow :3
// go play vivid/stasis now! https://vividstasis.gay
#define fo(i, a, b) for(auto i = (a); i < (b); i++)
#define pb push_back
#define f first
#define s second
#define be(a) a.begin(), a.end()
using namespace std;
int sum[1500], f[1500], b[1500];
long long find_maximum(int k, vector<vector<int>> d) {
int n = d.size();
int m = d[0].size();
vector<pair<long long, pair<int, int>>> V;
long long ans = 0;
vector<vector<pair<long long, int>>> d2(n);
fo(i, 0, n) fo(j, 0, m) d2[i].pb({d[i][j], j});
fo(i, 0, n) {
sort(be(d2[i]));
fo(j, 0, k) V.pb({d2[i][m-1-j].f + d2[i][k-1-j].f, {i, j}}), ans -= d2[i][j].f;
}
sort(be(V), [](pair<long long, pair<int, int>> a, pair<long long, pair<int, int>> b) { return a.f != b.f ? a.f > b.f : a.s < b.s; });
fo(i, 0, n * k / 2) ans += V[i].f, sum[V[i].s.f] = V[i].s.s + 1;
vector<vector<int>> res(n, vector<int>(m, -1));
fo(i, 0, k) {
vector<pair<int, int>> v;
fo(j, 0, n) v.pb({sum[j], j});
sort(be(v));
fo(j, 0, n / 2) res[v[j].s][d2[v[j].s][ f[v[j].s] ].s] = i, f[v[j].s]++;
fo(j, n / 2, n) res[v[j].s][d2[v[j].s][m-b[v[j].s]-1].s] = i, b[v[j].s]++, sum[v[j].s]--;
}
allocate_tickets(res);
return ans;
}
