#include <bits/stdc++.h>
#include "tickets.h"
#define DIM 2000
#define INF 2000000000000000000LL
using namespace std;
int n,m;
long long dp[DIM][DIM];
int t[DIM][DIM];
pair <int,int> poz[DIM];
long long find_maximum (int k, vector<vector<int> > x){
n = x.size(), m = x[0].size();
int i,j;
vector <pair<int,int> > v;
vector <vector<int> > ans;
ans.resize(n);
for (i=0;i<n;i++)
ans[i].resize(m,-1);
for (i=0;i<n;i++)
poz[i].first = 0, poz[i].second = m-1;
long long sum = 0;
for (int pas=0;pas<k;pas++){
/// dp[i][j] - suma maxima daca am selectat i culori si am j plusuri
/// poz[i] - capetele stanga dreapta unde am ramas la fiecare culoare
for (i=0;i<=n;i++)
for (j=0;j<=n/2;j++)
dp[i][j] = -INF, t[i][j] = 0;
dp[0][0] = 0;
for (i=1;i<=n;i++){
while (ans[i-1][poz[i-1].first] != -1)
poz[i-1].first++;
while (ans[i-1][poz[i-1].second] != -1)
poz[i-1].second--;
for (int j=0;j<=n/2;j++){ /// vreau sa am j plusuri
if (i - j > n/2) /// am prea multe minusuri
continue;
/// iau din stanga => -
if (dp[i-1][j] != -INF && dp[i-1][j] - x[i-1][poz[i-1].first] > dp[i][j]){
dp[i][j] = dp[i-1][j] - x[i-1][poz[i-1].first];
t[i][j] = 1;
}
/// iau din dreapta => +
if (j && dp[i-1][j-1] != -INF && dp[i-1][j-1] + x[i-1][poz[i-1].second] > dp[i][j]){
dp[i][j] = dp[i-1][j-1] + x[i-1][poz[i-1].second];
t[i][j] = 0;
}
}
}
sum += dp[n][n/2];
int idx = n, nr = n/2;
while (idx){
if (t[idx][nr])
ans[idx-1][poz[idx-1].first] = pas;
else {
ans[idx-1][poz[idx-1].second] = pas;
nr--;
}
idx--;
}
}
allocate_tickets(ans);
return sum;
}
