#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
struct cell {
int i, j, val;
};
const int MAX_N = 1500;
const int MAX_M = 1500;
int x[MAX_N + 1][MAX_M + 1], l[MAX_N];
long long sx[MAX_N + 1][MAX_M + 1];
vector<int> mins[MAX_N + 1], maxs[MAX_N + 1];
vector<cell> opt;
long long find_maximum( int k, vector<vector<int>> X ) {
int n = X.size();
int m = X[0].size();
vector<vector<int>> answer( n );
long long sum = 0;
for ( int i = 1; i <= n; i++ ) {
answer[i - 1].resize( m );
for ( int j = 1; j <= m; j++ ) {
x[i][j] = X[i - 1][j - 1];
sx[i][j] = sx[i][j - 1] + x[i][j];
answer[i - 1][j - 1] = -1;
}
}
for ( int i = 1; i <= n; i++ ) {
for ( int j = 1; j <= k; j++ ) {
mins[i].push_back( j );
opt.push_back( { i, m - (k - j), x[i][j] + x[i][m - (k - j)] } );
}
}
sort( opt.begin(), opt.end(), []( cell a, cell b ) {
if ( a.val == b.val )
return a.j > b.j;
return a.val > b.val;
} );
for ( int i = 0; i < n * k / 2; i++ ) {
mins[opt[i].i].pop_back();
maxs[opt[i].i].push_back( opt[i].j );
}
for ( int i = 1; i <= n; i++ ) {
reverse( maxs[i].begin(), maxs[i].end());
vector<pair<int, int>> pasi;
for ( int pas = 0; pas < k; pas++ )
pasi.push_back( { l[pas], pas } );
sort( pasi.begin(), pasi.end() );
int ind = 0;
for ( int j: mins[i] ) {
answer[i - 1][j - 1] = pasi[ind].second;
l[pasi[ind].second]++;
sum -= x[i][j];
ind++;
}
for ( int j: maxs[i] ) {
answer[i - 1][j - 1] = pasi[ind].second;
sum += x[i][j];
ind++;
}
}
allocate_tickets( answer );
return sum;
}
