//Thank you
#include"tickets.h"
#ifndef EVAL
#include"stub.cpp"
#endif
#include<bits/stdc++.h>
using namespace std;
int l[1505],r[1505];
typedef long long ll;
bool cmp(int x,int y){return (l[x]>l[y]);}
long long find_maximum(int k,vector<vector<int> > arr) {
priority_queue<pair<ll,int>>q;ll res=0;
int n=arr.size(),m=arr[0].size();vector<int>ind(n);
vector<vector<int>>answer(n,vector<int>(m,-1));
for(int i=0;i<n;i++){ind[i]=i;
for(int j=0;j<k;j++)res-=arr[i][j];
q.push({arr[i][l[i]=k-1]+arr[i][r[i]=m-1],i});
}
for(int i=0;i<(n*k)>>1;i++){
int ind=q.top().second;res+=q.top().first;q.pop();--l[ind];--r[ind];
if(l[ind]>=0)q.push({arr[ind][l[ind]]+arr[ind][r[ind]],ind});
}
while(k--){sort(ind.begin(),ind.end(),cmp);
for(int i=0;i<n>>1;i++)answer[ind[i]][l[ind[i]]--]=k;
for(int i=n>>1;i<n;i++)answer[ind[i]][++r[ind[i]]]=k;
}
allocate_tickets(answer);
return res;
}
