#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<int> dp(2*n+1,-1e15);
vector<vector<pair<int,int>>> last(n, vector<pair<int,int>>(2*n+1));
dp[n]=0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < sz(dp); j++){
if(((int)abs(j-n))%2!=i%2) dp[j]=-1e15;
}
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=j;
}
if(mx<x[i][j]){
mx=x[i][j];
mxI=j;
}
}
for (int j = n-i; j <= n+i; j++)
{
if(((int)abs(j-n))%2!=i%2) continue;
if(dp[j-1]<dp[j]+MAX-mn){
dp[j-1]=dp[j]+MAX-mn;
last[i][j-1]={mnI,-1};
}
if(dp[j+1]<dp[j]-MAX+mx){
dp[j+1]=dp[j]-MAX+mx;
last[i][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];
}
