#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 ansL(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();
int id = x.id + 1, c = x.color;
if (id == K) ansL[c] = K;
else Q.push(Node(a[c][id] + a[c][M - K + id], id, c));
}
while (!Q.empty()) ansL[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 ansL[a] > ansL[b];});
for (int i = 0; i < N; ++i) {
int p = pos[i];
if (i < (N >> 1)) g[p][--ansL[p]] = k, ans -= a[p][ansL[p]];
else g[p][M - (++cntR[p])] = k, ans += a[p][M - cntR[p]];
}
}
allocate_tickets(g);
return ans;
}
