#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
long long find_maximum(int k, vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector <vector <int>> ans(n, vector <int> (m, -1));
ll sum = 0;
vector <multiset<pair<int,int>>> rows(n);
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
rows[i].insert({x[i][j], j});
}
}
for (int i = 0; i < k; i++){
ll cur = 0;
vector <pair<ll, int>> ticket;
for (int j = 0; j < n; j++){
pair<int, int> l = *rows[j].begin();
pair<int, int> r = *rows[j].rbegin();
ll cur = -l.first - r.first;
ticket.push_back({cur, j});
cur += r.first;
}
sort(ticket.begin(), ticket.end(), greater<pair<ll, int>>());
for (int j = 0; j < n/2; j++){
if (rows[j].size() != 1){
cur += ticket[j].first;
}
else{
cur += 2*ticket[j].first;
}
int pos = ticket[j].second;
pair<int, int> ans_pos = *rows[pos].begin();
ans[pos][ans_pos.second] = i;
}
for (int j = 0; j < n; j++){
pair<int, int> ans_pos = *rows[j].begin();
pair<int, int> ans_pos_r = *rows[j].rbegin();
if (ans[j][ans_pos.second] != i){
ans[j][ans_pos_r.second] = i;
}
}
for (int j = 0; j < n; j++){
pair<int, int> l = *rows[j].begin();
pair<int, int> r = *rows[j].rbegin();
if (rows[j].size() == 1){
rows[j].erase(l);
}
else{
if (ans[j][l.second] == i){
rows[j].erase(l);
}
else{
rows[j].erase(r);
}
}
}
sum = max(sum, cur);
}
allocate_tickets(ans);
return sum;
}
