#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
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));
int a[n], b[n];
for (int i = 0; i < n; i++)
{
a[i] = 0;
b[i] = m - 1;
}
long long ret = 0;
for (int g = 0; g < k; g++)
{
vector<int>vals;
for (int i = 0; i < n; i++)
vals.push_back(x[i][a[i]]);
long long mx[n / 2 + 2][n / 2 + 2];
for (int i = 0; i <= n / 2 + 1; i++)
for (int j = 0; j <= n / 2 + 1; j++)
mx[i][j] = -1e18;
mx[0][0] = 0;
for (int i = 0; i < n; i++)
{
for (int c = 0; c <= n / 2; c++)
{
int d = i - c;
if (d >= 0 && d <= n / 2)
{
mx[c][d + 1] = max(mx[c][d + 1], mx[c][d] + x[i][b[i]]);
mx[c + 1][d] = max(mx[c + 1][d], mx[c][d] - x[i][a[i]]);
}
}
}
int c = n / 2;
int d = n / 2;
for (int i = n - 1; i >= 0; i--)
{
if (c == 0)
{
ret += x[i][b[i]];
answer[i][b[i]] = g;
b[i]--;
d--;
}
else if (d == 0)
{
ret -= x[i][a[i]];
answer[i][a[i]] = g;
a[i]++;
c--;
}
else if (mx[c][d] == mx[c][d - 1] + x[i][b[i]])
{
ret += x[i][b[i]];
answer[i][b[i]] = g;
b[i]--;
d--;
}
else
{
ret -= x[i][a[i]];
answer[i][a[i]] = g;
a[i]++;
c--;
}
}
}
allocate_tickets(answer);
return ret;
}
