#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1507;
ll T[LIM][LIM], akt[LIM], n, m;
long long find_maximum(int k, vector<vector<int>>V) {
n=V.size();
m=V[0].size();
rep(i, n) rep(j, m) T[i][j]=V[i][j];
ll sum=0;
rep(i, n) rep(j, k) sum+=T[i][m-j-1];
priority_queue<pair<ll,int>>q;
rep(i, n) q.push({-T[i][0]-T[i][m-k], i});
rep(i, n*k/2) {
ll p=q.top().st, a=q.top().nd; q.pop();
sum+=p;
++akt[a];
if(akt[a]<k) q.push({-T[a][akt[a]]-T[a][m-k+akt[a]], a});
}
vector<vector<int>>ans;
rep(i, n) {
vector<int>p;
rep(j, m) p.pb(-1);
rep(j, akt[i]) p[j]=j;
for(int j=m-1; j>=m-k+akt[i]; --j) p[j]=k-m+j;
ans.pb(p);
}
allocate_tickets(ans);
return sum;
}
