#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<long long>> suf(n + 1, vector<long long> (m + 2));
vector<vector<long long>> pref(n + 1, vector<long long> (m + 1));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
pref[i][j] = pref[i][j - 1] + x[i - 1][j - 1];
}
for (int j = m; j >= 1; --j) {
suf[i][j] = suf[i][j + 1] + x[i - 1][j - 1];
}
}
int negs = n / 2 * k;
vector<vector<int>> path(n + 1, vector<int> (negs + 1));
vector<vector<long long>> dp(n + 1, vector<long long> (negs + 1));
fill(dp[0].begin(), dp[0].end(), -INF);
dp[0][negs] = 0;
for (int i = 1; i <= n; ++i) {// one indexing
fill(dp[i].begin(), dp[i].end(), -INF);
for (int j = negs; j >= 0; --j) {
for (int l = 0; l <= min(k, negs - j); ++l) {
long long c = dp[i - 1][j + l] - pref[i][l] + suf[i][m + 1 + l - k];
if (c > dp[i][j]) {
dp[i][j] = c;
path[i][j] = l;
}
}
}
}
vector<int> cnt_pos(k, k * n / 2);
vector<int> cnt_neg(k, k * n / 2);
vector<vector<int>> answer(n, vector<int> (m, -1));
int row = n, col = 0;
for (int i = 0; i < n; ++i) {
int negatives = path[row][col];
col = col + path[row][col];
row--;
int z = 0;
vector<bool> used(k);
for (int j = 0; j < k && z < negatives; ++j) {
if (cnt_neg[j]) {
used[j] = true;
answer[row][z++] = j;
cnt_neg[j]--;
}
}
assert(z == negatives);
z = 0;
for (int j = 0; j < k && z < k - negatives; ++j) {
if (!used[j] && cnt_pos[j]) {
answer[row][m - z - 1] = j;
cnt_pos[j]--;
z++;
}
}
assert(z == k - negatives);
}
allocate_tickets(answer);
return dp[n][0];
}
