#include "tickets.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const int MAX=1e9;
long long find_maximum(signed k, std::vector<std::vector<signed>> x) {
int n=sz(x);
int m=sz(x[0]);
vector<vector<int>> dp(n, vector<int>(2*n+1,-1e15));
vector<vector<pair<int,int>>> last(n, vector<pair<int,int>>(2*n+1));
for (int i = 0; i < m; i++)
{
dp[0][n-1]=MAX-x[0][i];
dp[0][n+1]=-(MAX-x[0][i]);
}
for (int i = 1; i < n; i++)
{
int mn=1e9;
int mnI=1e9;
int mx=0;
int mxI=0;
for (int j = 0; j < m; j++)
{
if(mn>x[i][j]){
mn=x[i][j];
mnI=i;
}
if(mx<x[i][j]){
mx=x[i][j];
mxI=j;
}
}
for (int j = -i; j <= i; j++)
{
if(dp[i][n+j-1]<dp[i-1][n+j]+MAX-mn){
dp[i][n+j-1]=dp[i-1][n+j]+MAX-mn;
last[i][n+j-1]={mnI,-1};
}
if(dp[i][n+j+1]<dp[i-1][n+j]-MAX+mn){
dp[i][n+j+1]=dp[i-1][n+j]-MAX+mn;
last[i][n+j+1]={mxI,1};
}
}
}
vector<vector<signed>> ret(n,vector<signed>(m,-1));
int rm=n;
for (int i = n-1; i>=0; i--)
{
ret[i][last[i][rm].first]=0;
rm-=last[i][rm].second;
}
allocate_tickets(ret);
return dp[n-1][n];
}
