#include "tickets.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
ll dp[1501][1501];
ll nextt[1501][1501];
long long find_maximum(int k, vector<vector<int>> x) {
ll n = x.size();
ll m = x[0].size();
vector<vector<int>> idk;
vector<vector<ll>> minmax;
FOR(i,0,n){
minmax.push_back({0,m-1});
}
FOR(i,0,755) FOR(j,0,1500) dp[i][j] = -2000000000000000;
dp[0][0] = 0;
FOR(i,0,n){
vector<int> temp;
FOR(j,0,m){
temp.push_back(-1);
}
idk.push_back(temp);
}
ll ans = 0;
FOR(p, 0, k){
FOR(i,0,n/2+2) FOR(j,0,n+1) dp[i][j] = -2000000000000000;
dp[0][0] = 0;
FOR(i,0,n/2+1){
FOR(j,0,n){
if (dp[i][j] + x[j][minmax[j][1]] > dp[i+1][j+1] ){
dp[i+1][j+1] = dp[i][j] + x[j][minmax[j][1]];
nextt[i+1][j+1] = -1;
}
if (dp[i][j] - x[j][minmax[j][0]] > dp[i][j+1]){
dp[i][j+1] = dp[i][j] - x[j][minmax[j][0]];
nextt[i][j+1] = 0;
}
}
}
ll hal = n/2;
ll cur = n;
while (cur != 0){
ll sus = nextt[hal][cur];
if (sus==-1){
idk[cur-1][minmax[cur-1][1]] = p;
minmax[cur-1][1] -= 1;
}else{
idk[cur-1][minmax[cur-1][0]] = p;
minmax[cur-1][0] += 1;
}
hal += sus;
cur -= 1;
}
ans += dp[n/2][n];
}
allocate_tickets(idk);
return ans;
}
