#include "tickets.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define Dval(c, i) d[c][O[c][i]]
using namespace std;
typedef long long LL;
typedef vector<int> Vec;
typedef pair<LL, LL> Pii;
LL find_maximum(int k, vector<Vec> d) {
LL n = d.size(), m = d[0].size();
vector<Vec> O(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) O[i].push_back(j);
sort(O[i].begin(), O[i].end(), [&](LL a, LL b) { return d[i][a] < d[i][b]; });
}
LL prize = 0;
Vec plus(n, 0), minus(n, 0), take(n, 0);
priority_queue<Pii> Q;
for (int c = 0; c < n; ++c) {
for (int j = 0; j < k; ++j) prize -= Dval(c, j);
Q.push(make_pair(Dval(c, k - 1) + Dval(c, m - 1), c));
}
for (int i = 0; i < n * k / 2; ++i) {
Pii it = Q.top(); Q.pop();
prize += it.first;
int c = it.second, &pc = plus[c];
if (++pc < k) Q.push(make_pair(Dval(c, k - 1 - pc) + Dval(c, m - 1 - pc), c));
}
while (!Q.empty()) Q.pop();
for (int c = 0; c < n; ++c) Q.push(make_pair(plus[c], c));
vector<Vec> S(n, Vec(m, -1));
for (int ki = 0; ki < k; ++ki) {
for (int i = 0; i < n / 2; ++i) take[Q.top().second] = 1, Q.pop();
for (int c = 0; c < n; ++c) {
int &p = plus[c];
Vec &s = S[c];
if (take[c]) s[O[c][m - p]] = ki, Q.push(make_pair(--p, c)), take[c] = 0;
else s[minus[c]++] = ki;
}
}
allocate_tickets(S);
return prize;
}
