#include "tickets.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
ll find_maximum(int k, vector<vector<int>> v){
int n = v.size(), m = v[0].size();
vector<ll> mn(n, 1e9+1), mx(n, -1);
for(int i = 0; i < n; i++)
mn[i] = *min_element(v[i].begin(), v[i].end()),
mx[i] = *max_element(v[i].begin(), v[i].end());
vector<vector<ll>> dp(n, vector<ll>(n/2+1, -1e18));
dp[n-1][0] = -mn[n-1];
dp[n-1][1] = mx[n-1];
for(int i = n-2; i >= 0; i--) for(int j = 0; j <= min(n/2, n-i); j++){
dp[i][j] = dp[i+1][j]-mn[i];
if(j != 0) dp[i][j] = max(dp[i][j], dp[i+1][j-1]+mx[i]);
}
vector<vector<int>> pos(n, vector<int>(m, -1));
ll ans = dp[0][n/2];
int c = n/2;
for(int i = 0; i < n; i++){
if(i == n-1){
if(c) pos[i][max_element(v[i].begin(), v[i].end())-v[i].begin()] = 0;
else pos[i][min_element(v[i].begin(), v[i].end())-v[i].begin()] = 0;
continue;
}
if(dp[i][c] == dp[i+1][c]-mn[i])
pos[i][min_element(v[i].begin(), v[i].end())-v[i].begin()] = 0;
else
pos[i][max_element(v[i].begin(), v[i].end())-v[i].begin()] = 0;
}
allocate_tickets(pos);
return ans;
}
