#include<bits/stdc++.h>
#include "tickets.h"
#include <vector>
#define ll long long
using namespace std;
const long long N = 85;
vector <vector <int>> x;
long long n, m, k;
long long l[N], r[N];
long long cnt[N];
long long ans[N][N];
long long dp[N][N*N];
long long best[N][N*N];
long long pref[N][N];
vector <vector <int>> answer;
/*
X <= (N/2)*K
dp[i][j] = estou na linha i e quero pegar j bons
O(n*n*k*m)
*/
long long query(long long linha, long long l, long long r){
if(r < l) return 0;
if(l == 0) return pref[linha][r];
return pref[linha][r]-pref[linha][l-1];
}
void solve(){
memset(ans, -1, sizeof ans);
vector<array <long long, 3>> valores;
for(long long i = 0;i < n;i++){
cnt[i] = 0;
for(long long j = 0;j <= l[i];j++){
valores.push_back({x[i][j], i, j});
}
for(long long j = r[i];j < m;j++){
valores.push_back({x[i][j], i, j});
}
}
sort(valores.begin(), valores.end());
for(long long i = 0;i < (n/2)*k;i++){
cnt[valores[i][1]]++;
}
long long res = 0;
long long turno = 0;
for(long long i = 0;i < n;i++){
r[i] = m-1;
l[i] = 0;
}
for(long long i = 0;i < k;i++){
vector <pair <long long, long long>> contadores;
for(long long i = 0;i < n;i++){
contadores.push_back({cnt[i], i});
}
sort(contadores.begin(), contadores.end());
for(long long i = 0;i < n/2;i++){
swap(contadores[i].first, contadores[i].second);
ans[contadores[i].first][r[contadores[i].first]] = turno;
res += x[contadores[i].first][r[contadores[i].first]];
r[contadores[i].first]--;
}
for(long long i = n/2;i < n;i++){
swap(contadores[i].first, contadores[i].second);
ans[contadores[i].first][l[contadores[i].first]] = turno;
res -= x[contadores[i].first][l[contadores[i].first]];
l[contadores[i].first]++;
cnt[contadores[i].first]--;
}
turno++;
}
for(long long i = 0;i < n;i++){
vector <int> aux;
for(long long j = 0;j < m;j++){
aux.push_back(ans[i][j]);
}
answer.push_back(aux);
}
allocate_tickets(answer);
}
long long find_maximum(int kk, std::vector<std::vector<int>> xx) {
x = xx;
memset(ans, -1, sizeof ans);
n = x.size();
m = x[0].size();
k = kk;
vector<array <long long, 3>> valores;
for(long long i = 0;i < n;i++){
for(long long j = 0;j < m;j++){
valores.push_back({x[i][j], i, j});
pref[i+1][j] = (j == 0 ? 0 : pref[i+1][j-1]) + x[i][j];
}
}
sort(valores.begin(), valores.end());
for(long long i = 0;i < (n/2)*m;i++){
cnt[valores[i][1]+1]++;
}
dp[0][0] = 0;
for(long long i = 1;i <= n*k;i++){
dp[0][i] = -1e14;
}
for(long long i = 1;i <= n;i++){
for(long long j = 0;j <= (n/2)*k;j++){
dp[i][j] = -1e14;
best[i][j] = -1;
for(long long t = 0;t <= k;t++){
if(j-t < 0) break;
if(dp[i][j] < dp[i-1][j-t] - query(i, 0, t-1) + query(i, m-(k-t), m-1)){
dp[i][j] = dp[i-1][j-t] - query(i, 0, t-1) + query(i, m-(k-t), m-1);
best[i][j] = t;
}
}
}
}
long long nn = n, qtd = (n/2)*k;
while(nn > 0){
long long v = best[nn][qtd];
l[nn-1] = v-1;
r[nn-1] = m-(k-v);
qtd -= v;
nn--;
}
solve();
return dp[n][(n/2)*k];
}
