#include "tickets.h"
#include <iostream>
#include <bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
int inf = 1e9 + 7;
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
vector<pair<int,int>> mini(n), maxi(n);
int m;
for (int i = 0; i < n; i++) {
m = x[i].size();
int mi = inf, ma = -1;
for (int j = 0; j < m; j++) {
mi = min(mi, x[i][j]);
ma = max(ma, x[i][j]);
}
mini[i] = {mi, i};
maxi[i] = {ma, i};
}
vector<pair<int, int>> comi = mini, coma = maxi;
sort(mini.begin(), mini.end());
sort(maxi.rbegin(), maxi.rend());
vector<bool> ismi(n), isma(n);
for (int i = 0; i < n / 2; i++) {
ismi[mini[i].se] = 1;
isma[maxi[i].se] = 1;
}
vector<ll> a, b;
for (int i = 0; i < n; i++) {
if (ismi[i]) {
a.push_back(comi[i].fi);
} else {
a.push_back(coma[i].fi);
}
if (isma[i]) {
b.push_back(coma[i].fi);
} else {
b.push_back(comi[i].fi);
}
}
sort(b.begin(), b.end());
sort(a.begin(), a.end());
ll mida = a[n / 2], midb = b[n / 2];
ll resa = 0, resb = 0;
for (auto el : a) {
resa += abs(el - mida);
}
for (auto el : b) {
resb += abs(el - midb);
}
vector<vector<int>> s(n, vector<int>(m, -1));
if (resa > resb) {
for (int i = 0; i < n; i++) {
int mi = inf, ma = -1;
int indmi = -1, indma = -1;
for (int j = 0; j < m; j++) {
mi = min(mi, x[i][j]);
ma = max(ma, x[i][j]);
if (mi == x[i][j])
indmi = j;
if (ma == x[i][j])
indma = j;
}
if (ismi[i]) {
s[i][indmi] = 0;
} else {
s[i][indma] = 0;
}
}
} else {
for (int i = 0; i < n; i++) {
int mi = inf, ma = -1;
int indmi = -1, indma = -1;
for (int j = 0; j < m; j++) {
mi = min(mi, x[i][j]);
ma = max(ma, x[i][j]);
if (mi == x[i][j])
indmi = j;
if (ma == x[i][j])
indma = j;
}
if (isma[i]) {
s[i][indma] = 0;
} else {
s[i][indmi] = 0;
}
}
}
allocate_tickets(s);
return max(resa, resb);
}
