#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) (int)(x).size()
#define all(x) begin(x), end(x)
using namespace std;
int n, m;
set <array <int, 3>> st;
vector <vector <int>> a, ans;
vector <int> l, r;
ll res;
void erase(int x, int y) {
st.erase({a[x][y], x, y});
if (l[x] == y) st.erase({a[x][r[x]], x, r[x]}), l[x]++;
else st.erase({a[x][l[x]], x, l[x]}), r[x]--;
}
void connect(int i, array <int, 3> & x, array <int, 3> & y) {
res += abs(x[0] - y[0]);
int A = x[1], B = x[2];
int C = y[1], D = y[2];
ans[A][B] = ans[C][D] = i;
erase(A, B), erase(C, D);
}
ll find_maximum(int k, vector<vector<int>> A) {
st.clear(), ans.clear();
n = A.size(), m = A[0].size(), a = A;
l = vector <int>(n, 0), r = vector <int>(n, m - 1);
res = 0;
for (int i = 0; i < n; i++)
ans.push_back(vector <int>(m, -1));
for (int it = 0; it < k; it++) {
for (int i = 0; i < n; i++) {
int L = l[i], R = r[i];
if (L > R) continue;
st.insert({a[i][L], i, L});
if (L != R)
st.insert({a[i][R], i, R});
}
while (SZ(st) > 1) {
auto x = *begin(st), y = *(--end(st));
if (x[1] == y[1]) {
auto x2 = *(++begin(st)), y2 = *(prev(--end(st)));
if (abs(x[0] - y2[0]) > abs(x2[0] - y[0]))
connect(it, x, y2);
else
connect(it, x2, y);
} else connect(it, x, y);
}
}
allocate_tickets(ans);
return res;
}
