#include<bits/stdc++.h>
#include "tickets.h"
#include <vector>
using namespace std;
struct getans{
long long sum; // ekhane
int row;
int col;
bool operator<( const getans& othe ) const {
if( sum != othe.sum ) return sum < othe.sum;
return col < othe.col;
}
};
int pos[2501] , neg[2501] , taken[2501] , jog , biyog;
long long find_maximum(int k, vector<vector<int>> xx) { // ekhane
long long uttor = 0; //ekhane
int n = (int)xx.size();
int m = (int)xx[0].size();
vector<vector<long long>> x;
vector<long long> lmao;
for( int z = 0; z < n; z++ ) {
lmao.clear();
for( int y = 0; y < m; y++ ) {
lmao.push_back((long long)xx[z][y]);
}
x.push_back(lmao);
}
vector<vector<int>> ans;
ans.clear();
vector<int> shuru(m , -1);
vector<getans> storeans;
storeans.clear();
for( int z = 0; z < n; z++ ) {
neg[z] = k;
ans.push_back(shuru);
for( int y = m - 1; y >= m - k; y-- ) {
getans lol;
lol.row = z;
lol.col = y;
lol.sum = x[z][y] + x[z][k - (m - y)];
storeans.push_back(lol);
}
}
sort(storeans.begin() , storeans.end() );
for( int z = (int)storeans.size() - 1; z >= (int)storeans.size() - ((n * k) / 2); z-- ) {
pos[storeans[z].row]++;
neg[storeans[z].row]--;
}
for( int z = 0; z < n; z++ ) {
cerr << pos[z] << " " << neg[z] << "\n";
}
for( int y = 0; y < k; y++ ) {
jog = n / 2;
biyog = n / 2;
for( int z = 0; z < n; z++ ) {
taken[z] = 0;
}
for( int z = 0; z < n; z++ ) {
if( pos[z] == 0 ) {
taken[z] = 1;
biyog--;
neg[z]--;
ans[z][neg[z]] = y;
uttor -= x[z][neg[z]];
}
else if( neg[z] == 0 ) {
taken[z] = 1;
jog--;
ans[z][m - pos[z]] = y;
uttor += x[z][m - pos[z]];
pos[z]--;
}
}
for( int z = 0; z < n; z++ ) {
if( taken[z] == 0 ) {
if( jog > 0 ) {
taken[z] = 1;
jog--;
ans[z][m - pos[z]] = y;
uttor += x[z][m - pos[z]];
pos[z]--;
}
else{
taken[z] = 1;
biyog--;
neg[z]--;
ans[z][neg[z]] = y;
uttor -= x[z][neg[z]];
}
}
}
}
allocate_tickets(ans);
return (long long)uttor;
}
