#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#include "tickets.h"
constexpr ll maxN = 1510;
vector<pair<ll, ll>> colours[maxN];
vector<vector<int>> ans;
long long find_maximum(int k, vector<vector<int>> a) {
ll coloursN = a.size();
ll n = a[0].size();
ll res=0;
for(int i = 0; i < coloursN; i++) {
vector<int> tmp;
for(int x = 0; x < n; x++) {
colours[i].push_back({a[i][x], x});
tmp.push_back({-1});
}
ans.push_back(tmp);
}
for(int i = 0; i < coloursN; i++)
sort(colours[i].begin(), colours[i].end());
priority_queue<pair<ll, pair<ll, pair<ll, ll>>>> q;
for(int i = 0; i < coloursN; i++) {
for(int x = 0; x < k; x++) {
res+=colours[i][x].first;
ans[i][colours[i][x].second]=x;
q.push({-colours[i][x].first-colours[i][n-k+x].first, {i, {x, n-k+x}}});
}
}
for(int i = 0; i < k*(coloursN/2); i++) {
pair<ll, pair<ll, pair<ll, ll>>> tmpPair = q.top();
q.pop();
res-= tmpPair.first;
ll color = tmpPair.second.first;
ll u = tmpPair.second.second.first;
ll v = tmpPair.second.second.second;
ans[color][v]=ans[color][u];
if(u!=v)ans[color][u]=-1;
}
allocate_tickets(ans);
return res;
}
