#include "tickets.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
long long solve(int k, vector<vector<int>>& x, vector<vector<int>>& ans){
int n = x.size();
int m = x[0].size();
vector<int> mx(n, -1) , mn(n, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (ans[i][j] == -1 && (mx[i] == -1 || x[i][mx[i]] < x[i][j])) mx[i] = j;
if (ans[i][j] == -1 && (mn[i] == -1 || x[i][mn[i]] > x[i][j])) mn[i] = j;
}
}
long long res = 0;
for (int i = 0; i < n; ++i) {
res += 1ll*x[i][mx[i]];
ans[i][mx[i]] = k;
}
vector<pair<int, int>> dif(n);
for (int i = 0; i < n; ++i) {
dif[i] = {x[i][mx[i]] + x[i][mn[i]], i};
}
sort(dif.begin(), dif.end());
for (int i = 0; i < n / 2; ++i) {
res -= 1ll*dif[i].first;
ans[dif[i].second][mx[i]] = -1;
ans[dif[i].second][mn[i]] = k;
}
return res;
}
long long find_maximum(int k, vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> ans(n, vector<int>(m, -1));
long long res = 0;
for (int i = 0; i < k; ++i) {
res += solve(i, x, ans);
}
allocate_tickets(ans);
return res;
}
