#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define lli long long int
#define pii pair<lli, lli>
#define rep(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 color first
#define pos second
#define maximo first
#define tipo second
#define chico 0
#define grande 1
lli suma;
lli mediana, gr, ch, a, b;
vi todos;
vector<vector<int> > respuesta;
pii dp[MAX_N][MAX_N];
pii tickets[MAX_N][MAX_N];
int usados[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){
tickets[i][j] = {x[i][j], j};
todos.push_back(x[i][j]);
}
sort(tickets[i], tickets[i] + m);
}
sort(todos.begin(), todos.end());
mediana = todos[(n * m) >> 1];
dp[0][0] = {tickets[0][m - 1].color - mediana, grande};
dp[0][1] = {mediana - tickets[0][0].color, chico};
rep(i, 1, n - 1) dp[i][0] = {dp[i - 1][0].maximo + tickets[i][m - 1].color - mediana, grande};
rep(i, 1, n - 1){
rep(j, 1, n / 2){
ch = dp[i - 1][j - 1].maximo + mediana - tickets[i][0].color;
gr = dp[i - 1][j].maximo + tickets[i][m - 1].color - mediana;
if (ch <= gr) dp[i][j] = {gr, grande};
else dp[i][j] = {ch, chico};
}
}
suma = dp[n - 1][n / 2].maximo;
a = n - 1;
b = n / 2;
while (a >= 0){
if (dp[a][b].tipo == grande) usados[a] = tickets[a][m - 1].pos;
else {
usados[a] = tickets[a][0].pos;
b--;
}
a--;
}
rep(i, 0, n - 1){
debug(usados[i]);
vector<int> bolsa(m);
rep(j, 0, m - 1){
if (j == usados[i]) bolsa[j] = 0;
else bolsa[j] = -1;
}
respuesta.push_back(bolsa);
}
allocate_tickets(respuesta);
return suma;
}
