#include <bits/stdc++.h>
#include "tickets.h"
using ll = long long;
using namespace std;
const int MAXN = 1510;
const ll INF = 1e18;
ll mn[MAXN], mx[MAXN];
ll dp[MAXN][MAXN];
ll find_maximum(int k, vector<vector<int>> x){
int n = x.size();
int m = x[0].size();
vector<vector<int>> ans;
for(int i=0; i<n; i++){
ans.push_back({});
for(int j=0; j<m; j++) ans[i].push_back(-1);
}
for(int i=0; i<=n; i++){
for(int j=0; j<=n; j++){
dp[i][j] = -INF;
}
}
dp[0][0] = 0;
for(int i=1; i<=n; i++){
int mn = x[i - 1][0], mx = x[i - 1][m - 1];
for(int j=0; j<=(n / 2); j++){
dp[i][j] = dp[i - 1][j] + mx;
if(j > 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] - mn);
}
}
int cur = n / 2;
for(int i=n; i>=1; i--){
int mn = x[i - 1][0], mx = x[i - 1][m - 1];
if(cur == 0 || dp[i - 1][cur] + mx == dp[i][cur]){
ans[i - 1][m - 1] = 0;
} else{
ans[i - 1][0] = 0;
cur --;
}
}
allocate_tickets(ans);
return dp[n][n / 2];
}
