#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e17;
void dbg(vector<ll> xx) {
cout << "DBG: ";
for (auto x: xx) cout << x << " ";
cout << "\n";
}
ll calc_cost(vector<ll> x) {
int n = x.size();
sort(x.begin(), x.end());
ll cost = 0;
for (int i = 0; i < n; i++) cost += abs(x[n/2] - x[i]);
return cost;
/*
ll currCost = 0;
for (int i = 1; i < n; i++) currCost += x[i] - x[0];
ll mn = currCost;
for (int i = 1; i < n; i++) {
ll dis = (x[i] - x[i-1]);
currCost += dis * i;
currCost -= dis * (n - i);
mn = min(mn, currCost);
}
return mn;*/
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> cons(n, vector<int>(m, -1));
/*
vector<ll> arr;
for (int i = 0; i < n; i++) arr.push_back(x[i][0]);
ll maxCost = calc_cost(arr);
int bestPref = -1;
for (int i = 0; i < n; i++) {
}*/
assert(k == 1);
ll maxCost = 0;
vector<pair<ll, int>> bon;
for (int i = 0; i < n; i++) {
maxCost -= x[i][0];
bon.push_back({x[i][0] + x[i].back(), i});
cons[i][0] = 0;
}
sort(bon.rbegin(), bon.rend());
for (int i = 0; i < n/2; i++) {
maxCost += bon[i].first;
cons[bon[i].second][0] = -1;
cons[bon[i].second].back() = 0;
}
allocate_tickets(cons);
return maxCost;
}
