#include "tickets.h"
#include "bits/stdc++.h"
#include <vector>
using namespace std;
typedef long long ll;
#define INF 100000000000007
map<ll,ll>mp[1507];
vector<vector<int> >ans;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
ll n = x.size();
ll m = x[0].size();
//ll to=n*m*2;
ll r[n+7][n*m*4+307],rs[n+7];
for(int i=0;i<=n*m*2+300;i++){
r[0][i]=-INF;
}
r[0][n*k*2]=0;
for(int i=1;i<=n;i++){
vector<int>ro;
ll a=0;
for(int j=0;j<=n*m*4+300;j++){
r[i][j]=-INF;
}
for(int j=0;j<m;j++){
ro.push_back(-1);
}
for(int j=0;j<k;j++){
a-=x[i-1][j];
}
ans.push_back(ro);
for(int j=k;j>=0;j--){
mp[i][k-j-j]=a;
if(j>0)a+=x[i-1][j-1]+x[i-1][m-1-(k-j)];
}
for(int j=-k;j<=k;j+=2){
for(int j1=max(0ll,n*k*2-i*k);j1<=min(n*m*4,n*k*2+i*k);j1++){
if(j1-j>=0)r[i][j1]=max(r[i-1][j1-j]+mp[i][j],r[i][j1]);
}
}
}
ll y=n*k*2;
ll s=r[n][n*k*2];
ll l=0;
for(int i=n;i>=1;i--){
for(int j=0;j<=k;j++){
ll t=k-j*2;
if(y-t>=0 && r[i-1][y-t]==s-mp[i][t]){
rs[i]=j;
s=r[i-1][y-t];
y-=t;
break;
}
}
ll h=l;
//cout<<i<<" "<<rs[i]<<endl;
for(int j=0;j<rs[i];j++){
ans[i-1][j]=(h%k);
h++;
//cout<<j<<" ";
}
// cout<<endl;
l=h;
for(int j=m-1;j>=m-(k-rs[i]);j--){
ans[i-1][j]=(h%k);
h++;
//cout<<j<<" ";
}
//cout<<endl;
}
allocate_tickets(ans);
return r[n][n*k*2];
}
