#include "tickets.h"
#include "bits/stdc++.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define le(x) ((x)[((int)(x).size())-1])
#define sz(x) ((int)((x).size()))
#define pb push_back
#define s second
#define f first
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MxN=1510, INF=1e9, LINF=1e18;
int n, m, l[MxN], r[MxN];
pii prv[MxN][MxN];
ll dp[MxN][MxN];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
n=sz(x); m=sz(x[0]);
assert(k==1);
FOR(i, 1, n+1) {
l[i]=x[i-1][0];
r[i]=x[i-1][m-1];
}
FOR(i, 0, n+1) FOR(j, 0, n+1) dp[i][j]=-LINF, prv[i][j]={-1,-1};
dp[0][0]=0;
FOR(i, 1, n+1) {
FOR(j, 0, i+1) {
if(j>=1) {
dp[i][j]=dp[i-1][j-1]+r[i];
prv[i][j]={i-1,j-1};
}
if(dp[i-1][j]-l[i]>dp[i][j]) {
dp[i][j]=dp[i-1][j]-l[i];
prv[i][j]={i-1,j};
}
}
}
vector b(n, vector(m, -1));
int i=n, j=n/2;
while(i>0) {
int x=prv[i][j].f, y=prv[i][j].s;
assert(x!=-1 && y!=-1);
if(y==j-1) b[i-1][m-1]=0;
else b[i-1][0]=0;
assert(x==i-1);
i=x; j=y;
}
allocate_tickets(b);
return dp[n][n/2];
}
/*
2 3 2
0 2 5
1 1 3
4 2 1
5 9
1 4
3 6
2 7
4 4 1
0 1 2 9
4 4 4 5
3 3 3 7
3 4 4 4
4 2 1
0 10
1 5
0 6
0 6
4 4 1
0 1 2 9
7 7 7 7
7 7 7 7
7 7 7 7
8 2 1
1 9
0 10
2 3
3 4
6 8
1 5
0 2
3 4
4 3 2
0 1 1
1 1 1
0 0 1
0 0 0
4 2 2
0 1
0 1
0 0
1 1
4 2 1
0 1
0 0
0 0
1 1
4 3 2
0 0 0
0 1 1
0 1 1
1 1 1
*/
