#include <bits/stdc++.h>
using namespace std;
#include "tickets.h"
long long find_maximum(int q,vector<vector<int>> A){
int n = A.size(),m = A[0].size();
long long res(0);
multiset<pair<int,int>,greater<pair<int,int>>> que;
for (int i(0);i < n;++i) for (int k(0);k < q;++k){
res -= A[i][k],que.emplace(A[i][k]+A[i].end()[k-q],i);
}
vector<int> B(n,q);
for (int i(0);i < n*q/2;++i){
auto [a,b] = *que.begin(); que.erase(que.begin());
--B[b],res += a;
}
vector R(n,vector<int>(m,-1));
vector<int> C(n,1);
for (int i(0);i < q;++i){
int t(0);
for (int k(0);k < n;++k) if (B[k]==0) R[k][m-C[k]++] = i,++t;
for (int k(0);k < n;++k) if (B[k]){
if (B[k]==q-i||t==n/2) R[k][--B[k]] = i;
else R[k][m-C[k]++] = i,++t;
}
}
allocate_tickets(R);
return res;
}
