#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
const ll N=1.5e3+10,INF=1e18;
ll t[N];
struct node{
ll num,val;
}a[N];
ll cmp(node a,node b){
return a.val<b.val;
}
long long find_maximum(int k, std::vector<std::vector<int> > x) {
n = x.size();
m = x[0].size();
vector<std::vector<int> > ans;
for (int i = 0; i < n; i++) {
vector<int> row;
for (int j = 0; j < m; j++) row.push_back(-1);
ans.push_back(row);
}
if(m==1){
for(int i=0;i<n;i++) ans[i][0]=0;
allocate_tickets(ans);
ll s=0;
for(int i=0;i<n;i++) t[i]=x[i][0];
sort(t,t+n);
for(int i=0;i<n/2;i++) s-=t[i];
for(int i=n/2;i<n;i++) s+=t[i];
return s;
}
else if(k==1){
ll s=0;
for(int i=0;i<n;i++) s+=x[i][n-1];
for(int i=0;i<n;i++) a[i]=(node){i,x[i][0]+x[i][n-1]};
sort(a,a+n,cmp);
for(int i=0;i<n/2;i++) s-=a[i].val,ans[ a[i].num ][0]=0;
for(int i=n/2;i<n;i++) ans[ a[i].num ][n-1]=0;
allocate_tickets(ans);
return s;
}
else{
ll s=0;
for(int i=0;i<k;i++){
for(int j=0;j<n;j++) s+=x[j][i+m-k];
for(int j=0;j<n;j++) a[j]=(node){j,x[j][i]+x[j][i+m-k]};
sort(a,a+n,cmp);
for(int j=0;j<n/2;j++) s-=a[j].val,ans[a[j].num][i]=i;
for(int j=n/2;j<n;j++) ans[a[j].num][i+m-k]=i;
allocate_tickets(ans);
}
return s;
}
return 1;
}
