//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 = 1600;
vector<int> pw[2][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) {
for (int j = 0; j < m; ++j) {
a.push_back({d[i][j], i, j});
}
}
sort(all(a));
ll ans = 0;
int required = n * k / 2;
for (int i = 0; required; ++i) {
auto [value, x, y] = a[i];
if (sz(pw[0][x]) < k) {
ans -= value;
pw[0][x].push_back(y);
--required;
}
}
required = n * k / 2;
for (int i = n * m; i-- && required; ) {
auto [value, x, y] = a[i];
if (sz(pw[0][x]) < k) {
ans += value;
pw[1][x].push_back(y);
--required;
}
}
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;
}
allocate_tickets(s);
return ans;
}
