#include "bits/stdc++.h"
#include "tickets.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
long long find_maximum(int k, vector<vector<int>> x) {
int n = sz(x);
int m = sz(x[0]);
vector pos(n, vector<int>(m, -1));
long long ans = 0;
vector<pii> v;
for (int i = 0; i < n; i++) {
ans += x[i][m - 1];
pos[i][m - 1] = 0;
v.push_back({-x[i][m - 1]-x[i][0], i});
}
sort(rall(v));
for (int i = 0; i < n / 2; i++) {
auto [val, id] = v[i];
ans += val;
pos[id][m - 1] = -1;
pos[id][0] = 0;
}
allocate_tickets(pos);
return ans;
}
