#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 less(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();
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;
}
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];
}
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);
}
