#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], ilea[LIM], ileb[LIM], n, m;
ll 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);
ans.pb(p);
}
rep(i, k) {
vector<pair<int,int>>p;
rep(j, n) p.pb({akt[j]-ilea[j], j});
sort(all(p));
reverse(all(p));
rep(j, n) {
int x=p[j].nd;
if(j<n/2) {
ans[x][ilea[x]]=i;
++ilea[x];
} else {
++ileb[x];
ans[x][m-ileb[x]]=i;
}
}
}
allocate_tickets(ans);
return sum;
}
