#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> ans(n, vector<int>(m, -1));
vector<vector<ll>> dp(n, vector<ll>(n/2+1, 1e15));
vector<vector<pii>> prev(n, vector<pii>(n/2+1));
dp[0][0]=0; prev[0][0]={-1, 0};
dp[0][1]=x[0][0]; prev[0][1]={-1, 0};
for(int i=1;i<n;i++){
for(int j=n/2;j>=0;j--){
dp[i][j]=dp[i-1][j]; prev[i][j]={i-1, j};
if(j && dp[i-1][j-1]+x[i][0]<dp[i][j]){
dp[i][j]=dp[i-1][j-1]+x[i][0];
prev[i][j]={i-1, j-1};
}
}
}
ll sum=0ll;
pii curr={n-1, n/2};
while(curr.fi!=-1){
pii ant=prev[curr.fi][curr.se];
if(ant.se==curr.se) ans[curr.fi][m-1]=0, sum+=x[curr.fi][m-1];
else ans[curr.fi][0]=0, sum-=x[curr.fi][0];
curr=ant;
}
allocate_tickets(ans);
return sum;
}
