#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
const ll INF = 4e18;
int nless(int b, vi &x) {
return upper_bound(all(x), b) - bg(x);
}
ll f(ll b, ll i, ll j, ll L, ll R) {
return (R - j*b) + (i*b - L);
}
ll findb(vi &x) {
int n = x.size();
vector<ll> pref(n+1); for (int i = 0; i < n; i++) pref[i+1] += pref[i] + x[i];
auto f = [&](int b) {
int i = nless(b, x);
int L = pref[i], R = pref[n] - pref[i];
return (R - (n-i) * b) + (i*b - L);
};
int lo = x[0], hi = x.back();
while (lo < hi) {
int mid = lo + (hi-lo)/2;
if (f(mid) < f(mid+1)) hi = mid;
else lo = mid + 1;
}
return f(lo);
// ll T = accumulate(all(x), 0LL); ll L = 0, R = T;
// ll best = -1, bestv = INF, prev = 0;
// for (int i = 0; i < x.size(); i++) {
// int lo = prev, hi = x[i];
// while (lo < hi) {
// int mid = lo + (hi-lo)/2;
// if (f(mid, i, n-i, L, R) < f(mid+1, i, n-i, L, R)) hi = mid;
// else lo = mid+1;
// }
// cout << bestv << " ";
// if (best == -1 || bestv > f(lo, i, n-i, L, R)) best = lo, bestv = f(lo, i, n-i, L, R);
// L += x[i]; R -= x[i]; prev = x[i];
// }
// cout << "\n";
// return bestv;
}
ll find_maximum(int k, vvi x) {
int n = x.size(), m = x[0].size();
vvi answer(n, vi(m, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
answer[i][j] = j;
}
}
allocate_tickets(answer);
vi f; for (int i = 0; i < n; i++) f.push_back(x[i][0]);
sort(all(f));
return findb(f);
}
