#include "tickets.h"
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int N, M, K;
vector< vector<int> > X;
vector<int> mv(1500, 0);
struct col
{
int i;
};
bool operator < (col A, col B)
{
int a = X[A.i][K-1 - mv[A.i]] + X[A.i][M-1 - mv[A.i]];
int b = X[B.i][K-1 - mv[B.i]] + X[B.i][M-1 - mv[B.i]];
if(a == b) return A.i < B.i;
else return a > b;
}
vector<int> ct_top(1500), ct_bottom(1500);
long long find_maximum(int k, vector< vector<int> > x)
{
X = x;
K = k;
N = x.size();
M = x[0].size();
set<col> S;
for(int i = 0; i < N; i++) S.insert(col{i});
for(int i = 0; i < N*K/2; i++)
{
// cerr << "move = " << i << '\n';
// for(col q:S) cerr << q.i << ' ' << mv[q.i] << ' ' << X[q.i][K-1 - mv[q.i]] + X[q.i][M-1 - mv[q.i]] << '\n';
int s = S.begin()->i;
S.erase(S.begin());
mv[s]++;
if(mv[s] < K)
S.insert(col{s});
}
// for(int i = 0; i < N; i++) cerr << mv[i] << ' ';
// cerr << '\n';
long long res = 0;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < K - mv[i]; j++)
res -= X[i][j];
for(int j = M - mv[i]; j < M; j++)
res += X[i][j];
}
vector< vector<int> > s(N, vector<int>(M, -1));
for(int i = 0; i < N; i++)
{
ct_top[i] = mv[i];
ct_bottom[i] = K - ct_top[i];
}
vector<int> I(N);
for(int i = 0; i < N; i++) I[i] = i;
for(int k = 0; k < K; k++)
{
sort(I.begin(), I.end(), [] (int c1, int c2)
{
return ct_top[c1] < ct_top[c2];
});
for(int i = 0; i < N/2; i++)
{
s[I[i]][ct_bottom[I[i]] - 1] = k;
ct_bottom[I[i]]--;
}
for(int i = N/2; i < N; i++)
{
s[I[i]][M - ct_top[I[i]]] = k;
ct_top[I[i]]--;
}
}
allocate_tickets(s);
return res;
}
