#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 izq[MAX_N], der[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){
vector<int> bolsa(m);
rep(j, 0, m - 1){
tickets[i][j] = {x[i][j], j};
todos.push_back(x[i][j]);
bolsa[j] = -1;
}
sort(tickets[i], tickets[i] + m);
izq[i] = 0;
der[i] = m - 1;
respuesta.push_back(bolsa);
}
sort(todos.begin(), todos.end());
mediana = todos[(n * m) >> 1];
rep(ronda, 0, k - 1){
dp[0][0] = {tickets[0][der[0]].color - mediana, grande};
dp[0][1] = {mediana - tickets[0][izq[0]].color, chico};
rep(i, 1, n - 1) dp[i][0] = {dp[i - 1][0].maximo + tickets[i][der[i]].color - mediana, grande};
rep(i, 1, n - 1){
rep(j, 1, n / 2){
ch = dp[i - 1][j - 1].maximo + mediana - tickets[i][izq[i]].color;
gr = dp[i - 1][j].maximo + tickets[i][der[i]].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){
respuesta[a][tickets[a][der[a]].pos] = ronda;
der[a]--;
}
else {
respuesta[a][tickets[a][izq[a]].pos] = ronda;
izq[a]++;
b--;
}
a--;
}
}
allocate_tickets(respuesta);
return suma;
}
