//Cgrader.cpp
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
using ll = long long;
using ld = long double;
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
const int N = 2100;
vector<int> pw[2][N];
vector<int> sorted[N];
ll find_maximum(int k, vector<vector<int>> d) {
int n = sz(d), m = sz(d[0]);
vector<tuple<int, int, int>> a;
for (int i = 0; i < n; ++i) {
sorted[i] = vector(m, 0);
iota(all(sorted[i]), 0);
sort(all(sorted[i]), [&](int x, int y) {
return tie(d[i][x], x) < tie(d[i][y], y);
});
for (int j = 0; j < m; ++j) {
a.push_back({d[i][j], i, j});
}
}
stable_sort(all(a));
ll ans = 0;
for (int i = 0; i < n * m; ++i) {
auto [val, x, y] = a[i];
if (sz(pw[0][x]) < k) {
ans -= val;
pw[0][x].push_back(y);
}
}
set<pair<int, int>> cands;
for (int j = 0; j < n; ++j) {
if (!sz(pw[0][j])) {
continue;
}
int cval = d[j][sorted[j][m - sz(pw[1][j]) - 1]] + d[j][pw[0][j].back()];
cands.insert({cval, j});
}
for (int i = 0; i < n * k / 2; ++i) {
auto [value, j] = *cands.rbegin();
ans += value;
pw[1][j].push_back(sorted[j][m - sz(pw[1][j]) - 1]);
pw[0][j].pop_back();
cands.erase(--cands.end());
if (sz(pw[0][j])) {
int cval = d[j][sorted[j][m - sz(pw[1][j]) - 1]] + d[j][pw[0][j].back()];
cands.insert({cval, j});
}
}
// int sz0 = 0, sz1 = 0;
// for (int i = 0; i < n; ++i) {
// vector<int> indexes = pw[0][i];
// indexes.insert(end(indexes), all(pw[1][i]));
// sort(all(indexes));
// assert(unique(all(indexes)) == end(indexes));
// assert(sz(pw[0][i]) + sz(pw[1][i]) == k);
// sz0 += sz(pw[0][i]);
// sz1 += sz(pw[1][i]);
// }
// assert(sz0 == n * k / 2 && sz1 == n * k / 2);
set<pair<int, int>> where;
for (int i = 0; i < n; ++i) {
where.insert({sz(pw[0][i]), i});
}
vector s(n, vector(m, -1));
for (int i = 0; i < k; ++i) {
set<pair<int, int>> nwhere;
auto it = where.begin();
for (int j = 0; j < n; ++j, ++it) {
auto [val, x] = *it;
if (2 * j >= n) {
s[x][pw[0][x].back()] = i;
pw[0][x].pop_back();
nwhere.insert({val - 1, x});
} else {
s[x][pw[1][x].back()] = i;
pw[1][x].pop_back();
nwhere.insert({val, x});
}
}
where = nwhere;
}
// vector<int> good(m, -1);
// iota(end(good) - k, end(good), 0);
// for (int i = 0; i < n; ++i) {
// auto c = s[i];
// sort(all(c));
// assert(good == c);
// }
allocate_tickets(s);
return ans;
}
