#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
typedef long long ll;
ll sub1and2(int k, vector<vector<int>> x) {
ll n = x.size(), m = x[0].size();
vector<vector<int>> res(n, vector<int>(m, -1));
ll sum = 0;
vector<ll> front(n, 0), back(n, m-1);
while (k--) {
vector<pair<ll, ll>> avgId(n);
for (int i = 0; i < n; i++) {
avgId[i] = {x[i][front[i]] + x[i][back[i]], i};
}
sort(avgId.begin(), avgId.end());
vector<ll> choices(n);
ll median = 0;
for (int i = 0; i < n/2; i++) {
choices[i] = x[avgId[i].second][front[avgId[i].second]];
res[avgId[i].second][front[avgId[i].second]] = k;
front[avgId[i].second]++;
median = max(median, choices[i]);
}
for (int i = n/2; i < n; i++) {
choices[i] = x[avgId[i].second][back[avgId[i].second]];
res[avgId[i].second][back[avgId[i].second]] = k;
back[avgId[i].second]--;
}
for (auto &e : choices) sum += abs(e - median);
}
allocate_tickets(res);
return sum;
}
ll sub3(int k, vector<vector<int>> x) {
ll n = x.size(), m = x[0].size();
vector<vector<int>> res(n, vector<int>(m, -1));
ll sum = 0;
vector<ll> front(n, 0), back(n, m-1);
vector<pair<ll, ll>> cnt(n);
for (int i = 0; i < n; i++) {
cnt[i].first = lower_bound(x[i].begin(), x[i].end(), 1) - x[i].begin();
cnt[i].second = i;
}
sort(cnt.begin(), cnt.end());
while (k--) {
ll temp = 0;
for (int i = 0; i < n/2; i++) {
res[cnt[i].second][back[cnt[i].second]] = k;
if (x[cnt[i].second][back[cnt[i].second]]) temp++;
else {
temp--;
cnt[i].first--;
}
back[cnt[i].second]--;
}
for (int i = n/2; i < n; i++) {
res[cnt[i].second][front[cnt[i].second]] = k;
if (x[cnt[i].second][front[cnt[i].second]]) temp++;
else {
temp--;
cnt[i].first--;
}
front[cnt[i].second]++;
}
sum += n/2 - abs(temp)/2;
sort(cnt.begin(), cnt.end());
}
allocate_tickets(res);
return sum;
}
ll find_maximum(int k, vector<vector<int>> x) {
if (k == 1) return sub1and2(k, x);
return sub3(k, x);
}
