#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
const int mxN = 1.5e3+6;
bool have_c[mxN][mxN]={};
void allocate_tickets(std::vector<std::vector<int>> _x);
long long find_maximum(int k, std::vector<std::vector<int>> d) {
srand(time(0));
const int n = d.size(); //colors
const int m = d[0].size(); //tickets per color
vector<vector<int64_t>> dp(n+1, vector<int64_t>(n*k/2+1, -1e18));
vector<vector<int64_t>> prev(n+1, vector<int64_t>(n*k/2+1));
dp[0][0] = 0;
// vector<vector<int64_t>> dp(n+1, vector<int64_t>(n*k/2+1, -1e18));
// vector<vector<int64_t>> prev(n+1, vector<int64_t>(n*k/2+1));
// dp[0][0] = 0;
vector<vector<int64_t>> val(n, vector<int64_t>(m+1, 0)); //what value gain by taking j with minus
for (int i = 0; i < n; ++i) {
int64_t res = 0;
for (int j = m-1; j >= m-k; --j) {
res += d[i][j];
}
int ptr = m-k;
val[i][0] = res;
for (int j = 1; j <= k; ++j) {
res -= d[i][ptr];
res -= d[i][j-1];
val[i][j] = res;
ptr++;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= n*k/2; ++j) {
if (dp[i][j] == -1e18) continue;
for (int take = 0; take <= k && j+take <= n*k/2; ++take) {
int64_t nxt_val = dp[i][j] + val[i][take];
if (nxt_val > dp[i+1][j+take]) {
dp[i+1][j+take] = nxt_val;
prev[i+1][j+take] = take;
}
}
}
}
int64_t ans = dp[n][(n*k)/2];
int64_t j = (n*k)/2;
vector<vector<int>> ans_c(n, vector<int>(m, -1));
vector<array<int, 3>> less, more;
for (int i = n; i > 0; --i) {
int take_here = prev[i][j];
int left = k-take_here;
for (int x = 0; x < take_here; ++x) {
less.push_back({d[i-1][x], i-1, x});
}
for (int x = m-1; x >= m-left; --x) {
more.push_back({d[i-1][x], i-1, x});
}
j -= take_here;
}
sort(less.begin(), less.end(), [&] (const auto& A, const auto& B) {
return A[1] > B[1];
});
sort(more.begin(), more.end(), [&] (const auto& A, const auto& B) {
return A[1] < B[1];
});
// for (int i = 0; i < less.size(); ++i) {
// cout << less[i][0] << " " << less[i][1] << " " << less[i][2] << endl;
// }
// cout << "\n";
// for (int i = 0; i < more.size(); ++i) {
// cout << more[i][0] << " " << more[i][1] << " " << more[i][2] << endl;
// }
// cerr << more.size() << " " << less.size() << "\n";
auto go = [&] () {
for (int i = 0; i < k; ++i) {
for (int j = 0; j < n; ++j) {
have_c[i][j] = false;
}
}
// random_shuffle(less.begin(), less.end());
// random_shuffle(more.begin(), more.end());
vector<bool> used(more.size(), false);
int ptr = 0;
for (int i = 0; i < less.size(); ++i) {
while (ptr < more.size() && used[ptr] == true) ++ptr;
bool ok = false;
for (int j = ptr; j < more.size(); ++j) {
if (used[j]) continue;
if (less[i][1] == more[j][1]) {
continue;
}
if (less[i][0] > more[j][0]) continue;
for (int x = 0; x < k; ++x) {
if (!have_c[x][less[i][1]] && !have_c[x][more[j][1]]) {
have_c[x][less[i][1]] = true;
have_c[x][more[j][1]] = true;
used[j] = true;
ans_c[less[i][1]][less[i][2]] = x;
ans_c[more[j][1]][more[j][2]] = x;
ok = true;
break;
}
}
if (!ok) continue;
break;
}
if (!ok) return false;
}
return true;
};
while (!go()) {
random_shuffle(more.begin(), more.end());
}
allocate_tickets(ans_c);
return ans;
}
