#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();
if (l != r){
ll cur = -l.first - r.first;
ticket.push_back({cur, j});
}
else{
ticket.push_back({-l.first, j});
}
cur += r.first;
}
sort(ticket.begin(), ticket.end(), greater<pair<ll, int>>());
// cout << "tickets: " << "\n";
// for (int j = 0; j < n; j++){
// cout << ticket[j].first << " " << ticket[j].second << "\n";
// }
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);
}
}
}
// cout << "ans :" << "\n";
// for (int j = 0; j < n; j++){
// for (int z = 0; z < m; z++){
// cout << ans[j][z] << " ";
// }
// cout << "\n";
// }
// cout << "cur : " << cur << "\n";
sum = max(sum, cur);
}
// cout << "max_sum: " << sum << "\n";
// cout << "allocate" << "\n";
allocate_tickets(ans);
return sum;
}
