#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;
deque<pair<int,int>> dqE;
deque<pair<int,int>> dqU;
for (int j = -k; j < sz(dp); j++)
{
int v=dp2[j+k]+pre[i][0];
if((j+k)%2) swap(dqE,dqU);
while (!dqE.empty())
{
if(dqE.back().second<j-k) dqE.pop_back();
else {
int cv=dqE.back().first+pre[i][(k-(dqE.back().second-j))/2];
if(cv<v) dqE.pop_back();
else break;
}
}
while (!dqE.empty())
{
if(dqE.front().second<j-k) dqE.pop_front();
else break;
}
dqE.push_back({dp2[j+k],j+k});
v=dqE.front().first+pre[i][(k-(dqE.front().second-j))/2];
int vk=(k-(dqE.front().second-j))/2;
if((j+k)%2) swap(dqE,dqU);
if(j<0) continue;
dp[j]=v;
last[i][j]=vk;
}
}
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];
}
