#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F3F3F3F3F
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer(n, vector<int> (m, -1));
vector<vector<long long>> pre(n, vector<long long> (m, 0)), suf(n, vector<long long> (m, 0));
vector<vector<long long>> dp(n, vector<long long> (k * n / 2 + 5, -inf)), take(n, vector<long long> (k * n / 2 + 5, -1));
vector<long long> taken(n, 0);
auto presum = [&](int i, int len)
{
if (!len) return 0LL;
return pre[i][len - 1];
};
auto sufsum = [&](int i, int len)
{
if (!len) return 0LL;
return suf[i][m - len];
};
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++) pre[i][j] = (j ? pre[i][j - 1] : 0) + x[i][j];
for (int j = m - 1; j >= 0; j--) suf[i][j] = (j + 1 < m ? suf[i][j + 1] : 0) + x[i][j];
}
for (int i = 0; i <= min(k, k * n / 2); i++)
{
dp[0][i] = sufsum(0, i) - presum(0, k - i);
take[0][i] = i;
}
for (int i = 1; i < n; i++)
{
for (int j = 0; j <= k * n / 2; j++)
{
for (int l = 0; l <= k; l++)
{
if (j - l < 0) continue;
if (dp[i - 1][j - l] + sufsum(i, l) - presum(i, k - l) > dp[i][j])
{
dp[i][j] = dp[i - 1][j - l] + sufsum(i, l) - presum(i, k - l);
take[i][j] = l;
}
}
}
}
int i = n - 1, j = n * k / 2;
int s = 0;
while (i >= 0)
{
taken[i] = take[i][j];
s += taken[i];
j -= take[i][j];
i--;
}
assert(j == 0);
vector<int> o(n, 0);
iota(o.begin(), o.end(), 0);
vector<int> l(n, 0), r(n, 0);
long long mn = -inf, mx = inf;
for (int i = 0; i < n; i++)
{
r[i] = m - taken[i];
for (int j = 0; j < k - taken[i]; j++) mn = max(mn, 1LL * x[i][j]);
for (int j = m - 1; j >= r[i]; j--) mx = min(mx, 1LL * x[i][j]);
}
assert(mn < mx);
for (int t = 0; t < k; t++)
{
sort(o.begin(), o.end(), [&](const int &a, const int &b)
{
return r[a] < r[b];
});
for (int i = 0; i < o.size() / 2; i++)
{
assert(r[o[i]] < m);
answer[o[i]][r[o[i]]] = t;
r[o[i]]++;
}
for (int i = o.size() / 2; i < o.size(); i++)
{
answer[o[i]][l[o[i]]] = t;
l[o[i]]++;
}
}
allocate_tickets(answer);
return dp[n - 1][n * k / 2];
}
