#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]);
int k=__k;
vector<int> dp(k*n*2+1,-1e15);
vector<int> dp2(k*n*2+1,-1e15);
vector<vector<int>> pre(n,vector<int>(k+1,0));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < k; j++) pre[i][k]+=MAX-x[i][j];
for (int j = k-1; j >= 0; j--) pre[i][j]=pre[i][j+1]-MAX+x[i][m-(k-j)]-MAX+x[i][j];
}
vector<vector<int>> last(n, vector<int>(k*n*2+1));
dp[n*k]=0;
for (int i = 0; i < n; i++)
{
swap(dp2,dp);
for (int j = 0; j < sz(dp); j++) dp[j]=-1e15;
for (int _k = k; _k >= 0; _k--)
{
for (int j = max(0LL,-(k-2*_k)); j+k-2*_k < sz(dp) && j < sz(dp2); j++)
{
//if(((int)abs(j-n))%2!=i%2) continue;
if(dp[j+k-2*_k]<dp2[j]+pre[i][_k]){
dp[j+k-2*_k]=dp2[j]+pre[i][_k];
last[i][j+k-2*_k]=_k;
}
}
}
}
vector<vector<signed>> ret(n,vector<signed>(m,-1));
set<pair<int,int>> st;
vector<int> stv(k,0);
for (int i = 0; i < k; i++) st.insert({stv[i],i});
int rm=n*k;
for (int i = n-1; i>=0; i--)
{
vector<pair<int,int>> ins;
for (int j = 0; j < last[i][rm]; j++) {
int v=(*st.rbegin()).second;
st.erase(*st.rbegin());
stv[v]--;
ins.push_back({stv[v],v});
ret[i][j]=v;
}
for (int j = m-(k-last[i][rm]); j < m; j++) {
int v=(*st.begin()).second;
st.erase(*st.begin());
stv[v]++;
ins.push_back({stv[v],v});
ret[i][j]=v;
}
for (int j = 0; j < k; j++) st.insert(ins[j]);
rm-=(k-2*last[i][rm]);
}
allocate_tickets(ret);
return dp[n*k];
}
