#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=1e6+10,LOG=17,mod=998244353;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define bt(i) (1 << (i))
//#define int ll
const ll inf=2e18;
#define y1 yy
#define prev pre
#define pii pair <int, int>
ll mni[maxn], mxi[maxn];
ll mx[maxn], mn[maxn];
bool cmp(pii a, pii b)
{
return a.f > b.f;
}
long long find_maximum(int k, vector <vector <int> > a)
{
vector <vector <int> > use;
int n = a.size();
int m = a[0].size();
use = a;
forn(0, i, n-1) forn(0, j, m-1) use[i][j] = -1;
vector <vector <pii> > b;
vector <vector <ll> > pref, suff, dp, pred;
pref.assign(n + 2, {});
suff.assign(n + 2, {});
dp.assign(n + 2, {});
pred.assign(n + 2, {});
b.assign(n + 2, {});
int SSS = k * n / 2;
forn(0, i, n + 1)
{
pred[i].assign(SSS + 2, 0);
dp[i].assign(SSS + 2, -inf);
b[i].assign(m + 2, mp(0, 0));
suff[i].assign(m + 2, 0);
pref[i].assign(m + 2, 0);
}
forn(1, i, n)
{
forn(1, j, m)
{
b[i][j] = {a[i-1][j-1], j};
}
sort(b[i].begin() + 1, b[i].begin() + 1 + m);
reverse(b[i].begin() + 1, b[i].begin() + 1 + m);
}
forn(1, i, n)
{
forn(1, j, m) pref[i][j] = pref[i][j - 1] + b[i][j].f;
nfor(1, j, m) suff[i][j] = suff[i][j + 1] + b[i][j].f;
}
ll ret = 0;
dp[0][0] = 0;
forn(1, i, n)
{
int bor = min((i-1) * k, SSS);
forn(0, j, bor)
{
forn(0, take, k)
{
if(take + j > SSS) break;
if(dp[i][take+j] < dp[i-1][j] + pref[i][take] -suff[i][m-k+take+1])
{
pred[i][take+j] = take;
dp[i][take+j]=dp[i-1][j]+pref[i][take]-suff[i][m-k+take+1];
}
}
}
}
int cur = SSS;
set <pii> st;
forn(0, i, k-1)
{
st.insert({0, i});
}
ret = dp[n][SSS];
nfor(1, i, n)
{
int take = pred[i][cur];
set <pii> nw;
forn(1, j, take)
{
use[i-1][b[i][j].s-1] = st.begin()->s;
pii temp = *st.begin();
st.erase(st.begin());
temp.f++;
nw.insert(temp);
}
forn(m - k + take + 1, j, m)
{
use[i-1][b[i][j].s-1] = st.rbegin()->s;
pii temp = *st.rbegin();
temp.f--;
st.erase(*st.rbegin());
nw.insert(temp);
}
st = nw;
cur -= take;
}
allocate_tickets(use);
return ret;
}
