#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool minimize(T& a, T b){
if(a > b){
a = b;
return true;
}
return false;
}
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
return true;
}
return false;
}
const int lim = 1505;
const int INF = 2e9;
int n, m, k, a[lim][lim];
namespace sub1{
ll solve(){
vector<int>A;
vector<vector<int>>s(n, vector<int>(m));
for(int i = 0; i < n; i++){
A.emplace_back(a[i][0]);
s[i][0] = 0;
}
allocate_tickets(s);
sort(A.begin(), A.end());
int median = A[n >> 1];
ll ans = 0;
for(int& x : A){
ans += abs(x - median);
}
return ans;
}
}
namespace sub2{
ll solve(){
vector<vector<int>>p(n, vector<int>(2));
for(int i = 0; i < n; i++){
if((p[i][0] = min_element(a[i], a[i] + m) - a[i]) == (p[i][1] = max_element(a[i], a[i] + m) - a[i])){
p[i][0] = 0;
p[i][1] = 1;
}
}
vector<pair<int, bool>>value;
for(int i = 0; i < n; i++){
value.emplace_back(i, false);
value.emplace_back(i, true);
}
sort(value.begin(), value.end(), [&] (auto i, auto j){
return a[i.first][p[i.first][i.second]] < a[j.first][p[j.first][j.second]];
});
vector<pair<int, int>>best;
ll ans = 0;
for(int i = 0; i < (n << 1); i++){
ll sum = -a[value[i].first][p[value[i].first][value[i].second]];
vector<int>cnt(n, 0);
vector<bool>use(n, false);
use[value[i].first] = true;
vector<pair<int, int>>state;
for(int j = i - 1; j > -1; j--){
if(++cnt[value[j].first] == 2){
state.emplace_back(value[j].first, p[value[j].first][value[j].second]);
sum -= a[value[j].first][p[value[j].first][value[j].second]];
use[value[j].first] = true;
}
}
for(int j = 0; j < i && state.size() + 1 < (n >> 1); j++){
if(!use[value[j].first]){
state.emplace_back(value[j].first, p[value[j].first][value[j].second]);
sum -= a[value[j].first][p[value[j].first][value[j].second]];
use[value[j].first] = true;
}
}
if(state.size() + 1 < (n >> 1)){
continue;
}
for(int j = (n << 1) - 1; j > i && state.size() + 1 < n; j++){
if(!use[value[j].first]){
state.emplace_back(value[j].first, p[value[j].first][value[j].second]);
sum += a[value[j].first][p[value[j].first][value[j].second]];
use[value[j].first] = true;
}
}
if(state.size() + 1 == n && maximize(ans, sum)){
state.emplace_back(value[i].first, p[value[i].first][value[i].second]);
best = state;
}
}
vector<vector<int>>s(n, vector<int>(m, -1));
for(auto& [i, j] : best){
s[i][j] = 0;
}
allocate_tickets(s);
return ans;
}
}
ll find_maximum(int _k, vector<vector<int>>_x){
n = _x.size();
m = _x[0].size();
k = _k;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
a[i][j] = _x[i][j];
}
}
if(m == 1){
return sub1::solve();
}
if(k == 1){
return sub2::solve();
}
}
