#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 result(vector<int> &s) {
int m = s.size();
sort(s.begin(), s.end());
ll mid = s[m / 2];
ll res = 0;
for (auto el : s) {
res += abs(mid - el);
}
return res;
}
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
vector<int> mini(n), maxi(n);
vector<int> indmini(n), indmaxi(n);
int m;
for (int i = 0; i < n; i++) {
m = x[i].size();
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;
}
mini[i] = mi;
indmini[i] = indmi;
maxi[i] = ma;
indmaxi[i] = indma;
}
vector<pair<vector<int>, vector<int>>> dp(n);
vector<vector<int>> par(n, {-1,-1});
dp[0].fi = {mini[0]};
dp[0].se = {maxi[0]};
vector<int> pr1, pr0;
for (int i = 1; i < n; i++) {
pr0 = dp[i - 1].fi;
pr1 = dp[i - 1].se;
pr0.push_back(mini[i]);
pr1.push_back(mini[i]);
if (result(pr0) > result(pr1)) {
dp[i].fi = pr0;
par[i][0] = 0;
} else {
dp[i].fi = pr1;
par[i][0] = 1;
}
pr0 = dp[i - 1].fi;
pr1 = dp[i - 1].se;
pr0.push_back(maxi[i]);
pr1.push_back(maxi[i]);
if (result(pr0) > result(pr1)) {
dp[i].se = pr0;
par[i][1] = 0;
} else {
dp[i].se = pr1;
par[i][1] = 1;
}
}
ll res;
int typ;
int cur = n - 1;
vector<vector<int>> s(n, vector<int>(m, -1));
if (result(dp[n - 1].fi) > result(dp[n - 1].se)) {
res = result(dp[n - 1].fi);
typ = 0;
} else {
res = result(dp[n - 1].se);
typ = 1;
}
while (cur != -1) {
if (typ == 0) {
s[cur][indmini[cur]] = 0;
} else {
s[cur][indmaxi[cur]] = 0;
}
typ = par[cur][typ];
cur--;
}
allocate_tickets(s);
return res;
}
