#include "tickets.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
ll dp[1501][1501];
ll nextt[1501][1501];
ll maxi = -1;
ll mini = -1;
long long find_maximum(int k, vector<vector<int>> x) {
ll n = x.size();
ll m = x[0].size();
vector<vector<int>> assigns;
FOR(i,0,n){
vector<int> temp;
FOR(j,0,m) temp.push_back(-1);
assigns.push_back(temp);
}
vector<vector<ll>> orders;
vector<vector<ll>> minmax;
FOR(i,0,n){
minmax.push_back({k,0});
}
FOR(i,0,n){
FOR(j,m-k,m){
orders.push_back({x[i][j]+x[i][j-(m-k)], i});
}
}
sort(orders.begin(), orders.end());
reverse(orders.begin(), orders.end());
ll top = 0;
FOR(i,0,orders.size()){
ll ind = orders[i][1];
//cout << ind <<" " << plus << endl;
if (minmax[ind][0]>0 && top < n*k/2){
minmax[ind][1] += 1;
minmax[ind][0] -= 1;
top += 1;
}
}
vector<vector<ll>> q;
for (auto&i : minmax) q.push_back(i);
FOR(i,0,n) q[i].push_back(i);
ll ans = 0;
ll cur = 0;
while (q[0][0] + q[0][1] > 0){
sort(q.begin(), q.end());
reverse(q.begin(), q.end());
FOR(i,0,n/2){
assigns[q[i][2]][q[i][0]-1] = cur;
q[i][0] -= 1;
ans -= x[q[i][2]][q[i][0]];
}
FOR(i,n/2,n){
assigns[q[i][2]][m-q[i][1]] = cur;
ans += x[q[i][2]][m-q[i][1]];
q[i][1] -= 1;
}
cur++;
}
allocate_tickets(assigns);
return ans;
}
