#include "tickets.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": "; for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())
const int inf=1000000100; // 1e9
const ll INF=10000000001000000; // 1e16
const int mod=1000000007;
const int MAXN=1510, LOG=20;
int n, m, k, x, y, u, v, t, a, b, ans;
int A[MAXN][MAXN], Ted[MAXN];
ll B[MAXN][MAXN];
vector<vi> out;
vi out1[MAXN], out2[MAXN];
vector<ll> dp[MAXN<<2];
vi par[MAXN<<2];
inline bool upd(ll &x, ll y){
if (x>=y) return 0;
x=y;
return 1;
}
void divide(int id, int tl, int tr){
dp[id].resize((tr-tl)*k+1);
par[id].resize((tr-tl)*k+1);
if (tr-tl==1){
for (int i=0; i<=k; i++) dp[id][i]=B[tl][i];
return ;
}
int mid=(tl+tr)>>1;
divide(id<<1, tl, mid);
divide(id<<1 | 1, mid, tr);
par[id][0]=0;
dp[id][0]=dp[id<<1][0]+dp[id<<1 | 1][0];
int x=0, y=0;
for (int i=1; i<SZ(dp[id]); i++){
if (x==SZ(dp[id<<1])-1) y++;
else if (y==SZ(dp[id<<1 | 1])-1) x++;
else{
ll valx=dp[id<<1][x+1]-dp[id<<1][x];
ll valy=dp[id<<1 | 1][y+1]-dp[id<<1 | 1][y];
if (valx>valy) x++;
else y++;
}
dp[id][i]=dp[id<<1][x]+dp[id<<1 | 1][y];
par[id][i]=x;
}
/*
cerr<<"\n";
debug2(tl, tr)
for (int i=0; i<SZ(dp[id]); i++) cerr<<dp[id][i]<<" ";
cerr<<"\n";
cerr<<"\n";*/
}
void Build(int id, int tl, int tr, int ted){
if (tr-tl==1){
Ted[tl]=ted;
return ;
}
int mid=(tl+tr)>>1;
Build(id<<1, tl, mid, par[id][ted]);
Build(id<<1 | 1, mid, tr, ted-par[id][ted]);
}
ll find_maximum(int _k, vector<vi> _A) {
n=SZ(_A);
m=SZ(_A[0]);
k=_k;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++) A[i][j]=_A[i-1][j-1];
for (int j=1; j<=k; j++) B[i][0]-=A[i][j];
for (int j=1; j<=k; j++) B[i][j]=B[i][j-1]+A[i][m-j+1]+A[i][k-j+1];
// B convex increasing
// B[j]<=B[j+1]
// B[j]-B[j-1]>=B[j+1]-B[j]
// debug2(B[i][0], B[i][1])
}
out.resize(n, vector<int>(m, -1));
divide(1, 1, n+1);
ll res=dp[1][n*k/2];
Build(1, 1, n+1, n*k/2);
for (int i=1; i<=n; i++){
for (int x=1; x<=k-Ted[i]; x++) out1[i].pb(x);
for (int x=0; x<Ted[i]; x++) out2[i].pb(m-x);
}
while (k--){
vector<pii> vec;
for (int i=1; i<=n; i++) vec.pb({SZ(out1[i]), i});
sort(all(vec));
for (int ii=1; ii<=n; ii++){
int i=vec[ii-1].second;
if (ii>n/2){
assert(SZ(out1[i]));
out[i-1][out1[i].back()-1]=k;
out1[i].pop_back();
}
else{
assert(SZ(out2[i]));
out[i-1][out2[i].back()-1]=k;
out2[i].pop_back();
}
}
}
allocate_tickets(out);
return res;
}
