#include <iostream>
#include "tickets.h"
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
int n,m;
int k;
vector<vector<int>> s,y;
int l[2000];
int r[2000];
int now[2000];
int hat[2000];
ll tot;
struct rem{
int col;
int ind;
};
rem nik[2500000];
bool cmp(rem al, rem be){
return y[al.col][al.ind-1] + y[al.col][al.ind-1+m-k] < y[be.col][be.ind-1] + y[be.col][be.ind-1+m-k];
}
bool cmp2(int ga, int de){
return hat[ga] > hat[de];
}
ll find_maximum(int ka, vector<vector<int>> x){
n = x.size();
m = x[0].size();
tot=0;
k=ka;
y = x;
s = x;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
s[i][j]=-1;
}
}
for(int i=0; i<n; i++){
l[i]=0;
r[i]=m-1;
}
for(int i=0; i<n; i++){
for(int j=1; j<=k; j++){
nik[(i*k) + j].col = i;
nik[(i*k) + j].ind = j;
}
}
sort(nik+1, nik+n*k+1, cmp);
for(int i=0; i<n; i++){
hat[i]=0;
}
for(int i=1; i<=n*k/2; i++){
hat[nik[i].col]++;
}
for(int ro=0; ro<k; ro++){
for(int i=0; i<n; i++){
now[i]=i;
}
sort(now, now+n, cmp2);
for(int i=n/2; i<n; i++){
tot += y[now[i]][r[now[i]]];
s[now[i]][r[now[i]]] = ro;
r[now[i]]--;
}
for(int i=0; i<n/2; i++){
tot -= y[now[i]][l[now[i]]];
hat[now[i]]--;
s[now[i]][l[now[i]]] = ro;
l[now[i]]++;
}
}
allocate_tickets(s);
return tot;
}
