#include "tickets.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using vi = vector<int>::iterator;
pair<ll, vector<vi>> get_ans_k1(vector<pair<vi, vi>>& x) {
int n = x.size();
ll ans = 0;
vector<vi> ansarr(n);
for (int i = 0; i < n; ++i)
ansarr[i] = x[i].first;
for (int i = 0; i < n; ++i) {
for (auto mdvl : {x[i].first, x[i].second}) {
int balance = 0;
vector<pair<ll, int>> balance_up;
vector<pair<ll, int>> balance_down;
ll cans = 0;
vector<vi> cansarr(n);
cansarr[i] = mdvl;
for (int j = 0; j < n; ++j) {
if (j == i)
continue;
if (*x[j].first <= *mdvl && *x[j].second >= *mdvl) {
ll add1 = *mdvl - *x[j].first;
ll add2 = *x[j].second - *mdvl;
if (add1 < add2) {
cansarr[j] = x[j].second;
balance_down.push_back({add2 - add1, j});
++balance;
} else {
cansarr[j] = x[j].first;
balance_up.push_back({add1 - add2, j});
--balance;
}
} else if (*x[j].first >= *mdvl) {
++balance;
cansarr[j] = x[j].second;
} else {
--balance;
cansarr[j] = x[j].first;
}
}
if (balance - 2 * int(balance_down.size()) > 1 || balance + 2 * int(balance_up.size()) < -1)
continue;
if (balance > 1) {
sort(balance_down.rbegin(), balance_down.rend());
while (balance_down.size() && balance > 1) {
int j = balance_down.back().second;
cansarr[j] = x[j].first;
balance -= 2;
balance_down.pop_back();
}
} else if (balance < -1) {
sort(balance_up.rbegin(), balance_up.rend());
while (balance_up.size() && balance < -1) {
int j = balance_up.back().second;
cansarr[j] = x[j].second;
balance += 2;
balance_up.pop_back();
}
}
cans = 0;
for (int j = 0; j < n; ++j)
cans += abs(*mdvl - *cansarr[j]);
if (cans > ans) {
ans = cans;
ansarr = cansarr;
}
}
}
return {ans, ansarr};
return {};
}
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> ansarr(n, vector<int>(m, -1));
ll ans = 0;
if (m == 1) {
vector<int> v;
for (int i = 0; i < n; ++i) {
ansarr[i][0] = 0;
v.push_back(x[i][0]);
}
sort(v.begin(), v.end());
int d = v[n / 2];
for (int i = 0; i < n; ++i)
ans += abs(d - v[i]);
} else if (n * k <= 100000000) {
vector<pair<vi, vi>> t(n);
for (int i = 0; i < n; ++i) {
t[i] = {x[i].begin(), x[i].end() - 1};
}
for (int qr = 0; qr < k; ++qr) {
auto [ca, cu] = get_ans_k1(t);
ans += ca;
for (int i = 0; i < n; ++i) {
if (t[i].first == cu[i])
++t[i].first;
else
--t[i].second;
ansarr[i][cu[i] - x[i].begin()] = qr;
}
}
}
allocate_tickets(ansarr);
return ans;
}
