#include "tickets.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
ll n = x.size();
ll m = x[0].size();
vector<vector<int>> ans(n,vector<int>(m,-1));
/*if (m == 1){
vector<ll> v;
for(ll i = 0;i<n;i++) {
v.push_back(x[i][0]);
ans[i][0] = 0;
}
allocate_tickets(ans);
sort(v.begin(),v.end());
ll sm = 0;
for(ll i : v) sm += abs(i-v[v.size()/2]);
return sm;
}*/
vector<deque<pair<ll,ll>>> a(n);
for(ll i = 0;i<n;i++){
for(ll j = 0;j<m;j++){
a[i].push_back({x[i][j],j});
}
sort(a[i].begin(),a[i].end());
}
ll sm = 0;
for(ll r = 0;r<k;r++){
/*for(ll i = 0;i<n;i++){
cerr << i << ":";
for(auto [v,j] : a[i]){
cerr << " " << v << "," << j;
}
cerr << "\n";
}*/
vector<pair<ll,ll>> ord;
for(ll i = 0;i<n;i++){
ord.push_back({a[i].front().first+a[i].back().first,i});
}
sort(ord.begin(),ord.end());
for(ll i = 0;i<n/2;i++){
auto [v,j] = a[ord[i].second].front();a[ord[i].second].pop_front();
ans[ord[i].second][j] = r;
//cerr << r << " -> " << ord[i].second << " " << j << "\n";
sm -= v;
}
for(ll i = n/2;i<n;i++){
auto [v,j] = a[ord[i].second].back();a[ord[i].second].pop_back();
ans[ord[i].second][j] = r;
//cerr << r << " -> " << ord[i].second << " " << j << "\n";
sm += v;
}
}
allocate_tickets(ans);
return sm;
}
