#include <bits/stdc++.h>
#include "tickets.h"
#define DIMN 1510
#define MLD 1000000000
using namespace std;
long long dp[DIMN][DIMN];
int tt[DIMN][DIMN] , prefix[DIMN] , sufix[DIMN];
int f[DIMN];
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size() , i , j;
int m = x[0].size();
long long sol = 0;
vector<vector<int>> answer;
for (i = 0; i < n; i++) {
vector<int> row;
row.resize(m , -1);
answer.push_back(row);
sufix[i] = m - 1;
}
for (int r = 0 ; r < k ; r++){
/// dp[i][j] = smin daca esti la linia i si ai selectat j din stanga
tt[0][0] = 1;
for (i = 1 ; i <= n ; i++){
for (j = 0 ; j <= n / 2 && j <= i ; j++){
if (j != 0){
if (!tt[i - 1][j] && tt[i - 1][j - 1]){
dp[i][j] = dp[i - 1][j - 1] + x[i - 1][prefix[i - 1]];
tt[i][j] = -1;
}
else if (!tt[i - 1][j - 1] && tt[i - 1][j]){
dp[i][j] = dp[i - 1][j] + MLD - x[i - 1][sufix[i - 1]];
tt[i][j] = 1;
}
else if (tt[i - 1][j - 1] && tt[i - 1][j]){
if (dp[i - 1][j] + MLD - x[i - 1][sufix[i - 1]] <= dp[i - 1][j - 1] + x[i - 1][prefix[i - 1]]){
dp[i][j] = dp[i - 1][j] + MLD - x[i - 1][sufix[i - 1]];
tt[i][j] = 1;
}
else {
dp[i][j] = dp[i - 1][j - 1] + x[i - 1][prefix[i - 1]];
tt[i][j] = -1;
}
}
}
else if (tt[i - 1][j]){
dp[i][j] = dp[i - 1][j] + MLD - x[i - 1][sufix[i - 1]];
tt[i][j] = 1;
}
}
}
sol += 1LL * MLD * n / 2 - dp[n][n / 2];
i = n;
j = n / 2;
while (i){
if (tt[i][j] == -1){
answer[i - 1][prefix[i - 1]] = r;
prefix[i - 1]++;
j--;
}
else {
answer[i - 1][sufix[i - 1]] = r;
sufix[i - 1]--;
}
i--;
}
}
allocate_tickets(answer);
return sol;
}
