#include<algorithm>
#include<vector>
#include<queue>
#include "tickets.h"
using namespace std;
typedef long long LL;
const int NN = 1508;
typedef vector<int> VI;
struct Node {
LL val;
int id, color;
Node(LL v = 0, int i = 0, int c = 0) : val(v), id(i), color(c) {}
bool operator < (const Node& nd) const { return val > nd.val; }
};
LL find_maximum(int K, vector<VI> a) {
priority_queue<Node> Q;
int N = a.size(), M = a[0].size();
VI cntL(N), cntR(N), pos(N);
for (int c = 0; c < N; ++c) // 每种颜色，本身已经递增排序了
Q.push(Node(a[c][0] + a[c][M - K], 0, c));
int cnt = N * K / 2;
for (int i = 1; i <= cnt; ++i) {
Node x = Q.top(); Q.pop(); // 选择一个最小的(Li+Ri)来减
int id = x.id + 1, c = x.color;
if (id == K) cntL[c] = K;
else Q.push(Node(a[c][id] + a[c][M - K + id], id, c));
}
while (!Q.empty()) cntL[Q.top().color] = Q.top().id, Q.pop();
LL ans = 0;
vector<VI> g(N, VI(M, -1));
for (int i = 0; i < N; ++i) pos[i] = i;
for (int k = 0; k < K; ++k) {
sort(pos.begin(), pos.end(), [&](int a, int b) {
return cntL[a] > cntL[b];
});
for (int c = 0; c < N; ++c) {
int p = pos[c], &cl = cntL[p], &cr = cntR[p];
if (2 * c < N) g[p][--cl] = k, ans -= a[p][cl];
else g[p][M - (++cr)] = k, ans += a[p][M - cr];
}
}
allocate_tickets(g);
return ans;
}
