#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pr pair
#define mpr make_pair
#define ff first
#define ss second
#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()
#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back
// -------------------- Solution -------------------- //
const int N = 85, M = 85;
deque<int> x[N], pp[N];
int ul[N], ur[N];
int n, m, k;
ll dp[N][N * M];
int from[N][N * M];
ll qry(int i, int l, int r)
{
if (l > r) return 0;
if (l == 0) return pp[i][r];
return pp[i][r] - pp[i][l - 1];
}
set<pr<int, int>> st1, st2;
deque<int> d1[N], d2[N];
multiset<int> st[N][N];
ll find_maximum(int k0, vector<vector<int>> x0)
{
int i, j;
n = x0.size();
m = x0[0].size();
k = k0;
for (i = 1; i <= n; i++) {
for (j = 0; j < m; j++) {
x[i].pb(x0[i - 1][j]);
if (j == 0) pp[i].pb(x0[i - 1][j]);
else pp[i].pb(pp[i].bk() + x0[i - 1][j]);
}
}
vector<vector<int>> res(n, vector<int>(m, -1));
ll ans = 0;
for (i = 0; i <= n + 1; i++) for (j = 0; j <= n * m + 1; j++) dp[i][j] = -ll(1e18);
dp[0][0] = 0;
int lim = k * n / 2;
for (i = 0; i < n; i++) {
for (j = 0; j <= min(i * m, lim); j++) {
if (dp[i][j] == -ll(1e18)) continue;
for (int kk = 0; kk <= k; kk++) {
if (j + kk <= lim && i * k - j + (k - kk) <= lim) {
if (dp[i + 1][j + kk] < dp[i][j] - qry(i + 1, 0, kk - 1) + qry(i + 1, m - (k - kk), m - 1)) {
dp[i + 1][j + kk] = dp[i][j] - qry(i + 1, 0, kk - 1) + qry(i + 1, m - (k - kk), m - 1);
from[i + 1][j + kk] = kk;
}
}
}
}
}
//for (i = 0; i <= n; i++) for (j = 0; j <= lim; j++) cout << i << ' ' << j << ' ' << dp[i][j] << "\n";
ans = dp[n][lim];
j = lim;
for (i = n; i >= 1; i--) {
int e = from[i][j];
ul[i] = e;
ur[i] = k - e;
j -= e;
}
/*for (i = 1; i <= n; i++) {
cout << ul[i] << ' ' << ur[i] << "\n";
}*/
for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) for (int kk = 0; kk < k; kk++) st[i][j].insert(kk);
for (i = 1; i <= n; i++) {
if (ul[i]) {
st1.insert(mpr(x0[i - 1][0], i));
for (j = 0; j < ul[i]; j++) d1[i].pb(x0[i - 1][j]);
}
if (ur[i]) {
st2.insert(mpr(x0[i - 1][m - ur[i]], i));
for (j = m - ur[i]; j < m; j++) d2[i].pb(x0[i - 1][j]);
}
}
for (int he = 0; he < lim; he++) {
pr<int, int> u = *st1.begin();
st1.erase(st1.begin());
d1[u.ss].popf();
if (!d1[u.ss].empty()) st1.insert(mpr(d1[u.ss].ft(), u.ss));
auto it = st2.begin(); if ((*it).ss == u.ss) it++;
pr<int, int> v = *it;
st2.erase(it);
d2[v.ss].popf();
if (!d2[v.ss].empty()) st2.insert(mpr(d2[v.ss].ft(), v.ss));
//cout << u.ff << ' ' << u.ss << ' ' << v.ff << ' ' << v.ss << "\n";
if (st[u.ss][v.ss].empty()) assert(false);
int de = *st[u.ss][v.ss].begin();
i = lower_bound(all(x0[u.ss - 1]), u.ff) - x0[u.ss - 1].begin();
j = lower_bound(all(x0[v.ss - 1]), v.ff) - x0[v.ss - 1].begin();
res[u.ss - 1][i] = res[v.ss - 1][j] = de;
for (i = 1; i <= n; i++) {
st[u.ss][i].erase(de);
st[i][u.ss].erase(de);
st[v.ss][i].erase(de);
st[i][v.ss].erase(de);
}
}
allocate_tickets(res);
return ans;
}
