#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const ll mxN=1505;
vll v[mxN][2];
ll ans[mxN][mxN];
ll sum;
}
long long find_maximum(int k, vector<vector<int>> a) {
memset(ans, -1, sizeof(ans));
ll n = a.size();
ll m = a[0].size();
sum=0;
vector<array<ll, 3>> tep;
for(ll i=0;i<n;i++){
for(ll j=0;j<k;j++){
sum-=a[i][j];
v[i][0].pb(j);
}
for(ll j=0;j<k;j++){
ll cur=a[i][m-1-j]+a[i][k-1-j];
tep.pb({cur, i, m-1-j});
}
}
sort(tep.begin(), tep.end(), greater<array<ll, 3>>());
for(ll rep=0;rep<n*k/2;rep++){
sum+=tep[rep][0];
v[tep[rep][1]][1].pb(tep[rep][2]);
v[tep[rep][1]][0].pop_back();
}
vector<array<ll, 2>> pq;
for(ll rep=0;rep<k;rep++){
pq.clear();
for(ll i=0;i<n;i++){
pq.pb({(ll) v[i][0].size(), i});
}
sort(pq.begin(), pq.end(), greater<array<ll, 2>>());
for(ll i=0;i<n/2;i++){
ll cur=v[pq[i][1]][0].back();
v[pq[i][1]][0].pop_back();
ans[pq[i][1]][cur]=rep;
}
for(ll i=n/2;i<n;i++){
ll cur=v[pq[i][1]][1].back();
v[pq[i][1]][1].pop_back();
ans[pq[i][1]][cur]=rep;
}
}
vector<vector<int>> re(n, vector<int>(m));
for(ll i=0;i<n;i++){
for(ll j=0;j<m;j++){
re[i][j]=(int) ans[i][j];
}
}
allocate_tickets(re);
return sum;
}
