#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 2010;
const int MAXA = 5e4+10;
const int SQRT = 300;
const ll INF = 2e18;
const int MOD = 1e9+7;
const int LOG = 20;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
int n, m, k;
int a[1510][1510];
int ty[MAXN];
long long find_maximum(int K, std::vector<std::vector<int>> x) {
n = x.size(); m = x[0].size(); k = K;
vector<pii> vec;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++) a[i][j] = x[i][j];
}
ll ans = 0;
for(int i=0; i<n; i++){
ans -= x[i][0];
vec.pb({x[i][0]+x[i][m-1], i});
}
sort(vec.rbegin(), vec.rend());
vector<vector<int>> answer;
for(int i=0; i<n/2; i++){
ans += vec[i].fi;
ty[vec[i].se] = 1;
}
for(int i=0; i<n; i++){
std::vector<int> row(m, -1);
if(ty[i] == 1){
row[m-1] = 0;
} else {
row[0] = 0;
}
answer.push_back(row);
}
allocate_tickets(answer);
return ans;
}
