#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
long long get(int k, vector<vector<int>> x, vector<vector<int>> g) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> a(k);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == -1) continue;
a[g[i][j]].push_back(x[i][j]);
}
}
long long ret = 0;
for (int i = 0; i < k; i++) {
sort(a[i].begin(), a[i].end());
long long sum = 0;
for (int j = 0; j < n; j++) {
if (j < n / 2) {
sum -= a[i][j];
} else {
sum += a[i][j];
}
}
ret += sum;
}
return ret;
}
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j) {
if (x[i][m - 1] == x[j][m - 1]) {
return x[i][0] > x[j][m - 1];
}
return x[i][m - 1] > x[j][m - 1];
});
vector<vector<int>> g(n, vector<int>(m, -1));
for (int i = 0; i < n; i++) {
if (i < n / 2) {
g[id[i]][m - 1] = 0;
} else {
g[id[i]][0] = 0;
}
}
long long ret = get(k, x, g);
auto ans = g;
sort(id.begin(), id.end(), [&](int i, int j) {
if (x[i][m - 1] == x[j][m - 1]) {
return x[i][0] < x[j][m - 1];
}
return x[i][m - 1] < x[j][m - 1];
});
g.assign(n, vector<int>(m, -1));
for (int i = 0; i < n; i++) {
if (i < n / 2) {
g[id[i]][0] = 0;
} else {
g[id[i]][m - 1] = 0;
}
}
if (get(k, x, g) > ret) {
ret = get(k, x, g);
ans = g;
}
allocate_tickets(ans);
return ret;
}
