#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
int n,m,l[1501],r[1501];
long long find_maximum(int k, vector<vector<int>> x){
n = x.size() , m = x[0].size();
vector<vector<int>> ans(n,vector<int>(m,-1));
vector<pair<int,int>> vals;
long long ret = 0;
priority_queue<pair<int,int>> pq;
for(int i = 0 ; i < n ; i += 1){
vals.push_back({0,i});
l[i] = k-1 , r[i] = m-1;
pq.push({x[i][k-1]+x[i][m-1],i});
}
for(int i = 0 ; i < (n*k)/2 ; i += 1){
pair<int,int> nxt = pq.top();
pq.pop();
vals[nxt.second].first += 1;
l[nxt.second] -= 1 , r[nxt.second] -= 1;
if(l[nxt.second] != -1){
pq.push({x[nxt.second][l[nxt.second]]+x[nxt.second][r[nxt.second]],nxt.second});
}
}
for(int i = 0 ; i < n ; i += 1){
l[i] = 0 , r[i] = m-1;
}
for(int i = 0 ; i < k ; i += 1){
sort(vals.begin(),vals.end());
for(int j = 0 ; j < n/2 ; j += 1){
int p = vals[j].second;
ret -= x[p][l[p]];
ans[p][l[p]] = i;
l[p] += 1;
}
for(int j = n/2 ; j < n ; j += 1){
int p = vals[j].second;
ret += x[p][r[p]];
ans[p][r[p]] = i;
r[p] -= 1;
vals[j].first -= 1;
}
}
allocate_tickets(ans);
return ret;
}
