#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define lli long long int
#define plii pair<lli, lli>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repa(i, a, b) for(int i = (a); i >= (b); i--)
#define debugsl(x) cerr << #x << " = " << x << ", "
#define debug(x) debugsl(x) << endl
#define MAX_N 1502
#define cant first
#define bolsa second
lli suma, a, b, num, mediana, offset;
vector<vector<int> > respuesta;
vector<int> mayores[MAX_N], menores[MAX_N], todos;
pii cantidadMayores[MAX_N];
long long find_maximum(int k, vector<vector<int> > x) {
int n = x.size();
int m = x[0].size();
rep(i, 0, n - 1)
rep(j, 0, m - 1)
todos.push_back(x[i][j]);
sort(todos.begin(), todos.end());
mediana = todos[(n * m >> 1) - 1];
if (mediana == todos[n * m - 1]) offset = 1;
rep(i, 0, n - 1){
vector<int> bolsa(m);
respuesta.push_back(bolsa);
cantidadMayores[i].bolsa = i;
rep(j, 0, m - 1){
if (x[i][j] + offset> mediana){
mayores[i].push_back(j);
cantidadMayores[i].cant++;
}
else menores[i].push_back(j);
}
}
rep(ronda, 0, k - 1){
sort(cantidadMayores, cantidadMayores + n); // ORDENA POR CANTIDAD DE UNOS
a = (n / 2) - 1;
repa(i, n - 1, n / 2){
b = cantidadMayores[i].bolsa;
if (mayores[b].size() > 0){
num = mayores[b].back();
respuesta[b][num] = ronda;
suma += x[b][num] - mediana;
mayores[b].pop_back();
cantidadMayores[i].cant--;
}
else{
a = i;
break;
}
}
repa(i, a, 0){
b = cantidadMayores[i].bolsa;
if (menores[b].size() > 0){
num = menores[b].back();
respuesta[b][num] = ronda;
menores[b].pop_back();
suma += mediana - x[b][num];
}
else {
num = mayores[b].back();
respuesta[b][b] = ronda;
mayores[b].pop_back();
cantidadMayores[i].cant--;
suma += x[b][num] - mediana;
}
}
}
rep(i, 0, n - 1){
while (mayores[i].size() > 0) { respuesta[i][mayores[i].back()] = -1; mayores[i].pop_back(); }
while (menores[i].size() > 0) { respuesta[i][menores[i].back()] = -1; menores[i].pop_back(); }
}
allocate_tickets(respuesta);
return suma;
}
