#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL<<(i))
namespace trung{
const ll MAXN = 1510;
pll ptr[MAXN];
ll a[MAXN][MAXN];
ll n,m;
}
long long find_maximum(int k, std::vector<std::vector<int>> d){
using namespace trung;
n=sz(d);
m=sz(d[0]);
for (ll i = 0;i < n;i ++)for (ll j = 0;j < m;j ++)a[i][j] = d[i][j];
for (ll i = 0;i < n;i ++)ptr[i] = MP(0,m-1);
vector <vector <ll> > res(n,vector <ll> (m,-1));
long long ans = 0;
for (ll i = 0;i < k;i ++){
vector <ll> order(n);
iota(order.begin(),order.end(),0);
sort(order.begin(),order.end(),
[&](ll x,ll y){
return a[x][ptr[x].fi] + a[x][ptr[x].se] < a[y][ptr[y].fi] + a[y][ptr[y].se];});
for (ll j = 0;j < n;j ++){
if (j < n/2){
res[order[j]][ptr[order[j]].fi] = i;
ans -= a[order[j]][ptr[order[j]].fi++];
}
else{
res[order[j]][ptr[order[j]].se] = i;
ans += a[order[j]][ptr[order[j]].se--];
}
}
}
allocate_tickets(res);
return ans;
}
