#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
#include "tickets.h"
using namespace std;
#define ll long long
vector<vector<ll>> x;
vector<vector<pair<ll, ll>>> dp;
ll n, m, k;
ll find_maximum(int k1, vector<vector<int>> x1){
k = k1;
n = x1.size();
m = x1[0].size();
x.assign(n, vector<ll>(m, 0));
vector<vector<int>> arr(n, vector<int>(m, -1));
ll ans = 0;
for(ll i = 0; i<n; i++) for(ll j = 0; j<m; j++) x[i][j] = (ll)x1[i][j];
vector<pair<ll, pair<ll, ll>>> gains;
vector<int> selBig(n, 0);
for(int i = 0; i<n; i++){
for(int j = 0; j<k; j++){
ans -= x[i][j];
gains.push_back({(x[i][j] + x[i][j+(m-k)]), {i, j}});
}
}
sort(gains.begin(), gains.end());
for(int i = k*n-1; i>=(k*n)/2; i--){
selBig[gains[i].second.first]++;
ans += gains[i].first;
}
priority_queue<pair<int, int>> pq;
for(int i = 0; i<n; i++) pq.push({selBig[i], i});
vector<int> smallIndx(n, 0);
for(int i = 0; i<n; i++) smallIndx[i] = k-selBig[i]-1;
for(int i = 0; i<k; i++){
vector<pair<int, int>> tmp;
for(int j = 0; j<n/2; j++){
arr[pq.top().second][m - pq.top().first] = i;
tmp.push_back({pq.top().first-1, pq.top().second});
pq.pop();
}
for(int j = 0; j<n/2; j++){
arr[pq.top().second][smallIndx[pq.top().second]] = i;
smallIndx[pq.top().second]--;
tmp.push_back({pq.top().first, pq.top().second});
pq.pop();
}
for(auto i : tmp) pq.push({i.first, i.second});
}
allocate_tickets(arr);
return ans;
}
// int main(void){
// freopen("input.txt", "r", stdin);
// ll n1, m1, k1;
// cin>>n1>>m1>>k1;
// vector<vector<int>> t;
// t.assign(n1, vector<int>(m1, 0));
// for(ll i = 0; i<n1; i++) for(ll j = 0; j<m1; j++) cin>>t[i][j];
// cout<<find_maximum(k1, t);
// }
