#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;
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>>left, right;
for(int j = i - 1; j > -1; j--){
if(++cnt[value[j].first] == 2){
left.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;
}
}
fill(cnt.begin(), cnt.end(), 0);
for(int j = i + 1; j < (n << 1); j++){
if(++cnt[value[j].first] == 2){
right.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(left.size() < (n >> 1) && right.size() <= (n >> 1)){
vector<int>index, lv(n), rv(n), lp(n), rp(n);
for(int j = 0; j < i; j++){
if(!use[value[j].first]){
index.emplace_back(value[j].first);
lv[value[j].first] = a[value[j].first][lp[value[j].first] = p[value[j].first][value[j].second]];
}
}
for(int j = i + 1; j < (n << 1); j++){
if(!use[value[j].first]){
rv[value[j].first] = a[value[j].first][rp[value[j].first] = p[value[j].first][value[j].second]];
}
}
int median = a[value[i].first][p[value[i].first][value[i].second]];
sort(index.begin(), index.end(), [&] (int x, int y){
return abs(lv[x] - median) - abs(rv[x] - median) > abs(lv[y] - median) - abs(rv[y] - median);
});
for(int j = (n >> 1) - int(left.size()) - 1; j > 0; ){
sum -= lv[index[--j]];
left.emplace_back(index[j], lp[index[j]]);
}
for(int j = (n >> 1) - int(right.size()); j > 0; j--){
int t = int(index.size()) - j;
sum += rv[index[t]];
right.emplace_back(index[t], rp[index[t]]);
}
if(maximize(ans, sum)){
left.emplace_back(value[i].first, p[value[i].first][value[i].second]);
swap(best, left);
for(auto& it : right){
best.emplace_back(it);
}
}
}
}
vector<vector<int>>s(n, vector<int>(m, -1));
for(auto& [i, j] : best){
s[i][j] = 0;
}
allocate_tickets(s);
return ans;
}
}
namespace sub4{
ll solve(){
vector<pair<int, int>>p;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
p.emplace_back(i, j);
}
}
sort(p.begin(), p.end(), [&] (auto i, auto j){
return a[i.first][i.second] > a[j.first][j.second];
});
vector<vector<bool>>big(n, vector<bool>(m, false));
for(int i = (n * m) >> 1; i > 0; ){
i--;
big[p[i].first][p[i].second] = true;
}
vector<vector<int>>ans(n, vector<int>(m));
ll sum = 0;
deque<pair<int, int>>dq;
for(int i = 0; i < m; i++){
dq.emplace_back(n >> 1, i);
}
for(int i = 0; i < n; i++){
for(int t = 0; t < m; t++){
if(big[i][t]){
sum += a[i][t];
auto [u, v] = dq.front();
dq.pop_front();
if(u > 0){
dq.emplace_back(u - 1, v);
}
ans[i][t] = v;
}
}
}
for(int i = 0; i < n; i++){
vector<bool>use(m, false);
for(int t = 0; t < m; t++){
if(big[i][t]){
use[ans[i][t]] = true;
}
}
vector<int>I;
for(int t = 0; t < m; t++){
if(!use[t]){
I.emplace_back(t);
}
}
for(int t = 0; t < m; t++){
if(!big[i][t]){
sum -= a[i][t];
ans[i][t] = I.back();
I.pop_back();
}
}
}
allocate_tickets(ans);
return sum;
}
}
namespace sub3567{
ll solve(){
ll sum = 0;
vector<tuple<int, int, int, int>>greed;
vector<vector<int>>ans(n, vector<int>(m, -1));
for(int i = 0; i < n; i++){
vector<int>p(m);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&] (int x, int y){
return a[i][x] < a[i][y];
});
for(int j = 0; j < k; j++){
sum -= a[i][p[j]];
ans[i][p[j]] = -2;
greed.emplace_back(i, p[j], p[m - k + j], j);
}
}
sort(greed.begin(), greed.end(), [&] (auto i, auto j){
auto& [xi, yi1, yi2, pi] = i;
auto& [xj, yj1, yj2, pj] = j;
int sum_i = a[xi][yi1] + a[xi][yi2], sum_j = a[xj][yj1] + a[xj][yj2];
return sum_i > sum_j || (sum_i == sum_j && pi > pj);
});
for(int i = 0; i < ((n * k) >> 1); i++){
auto [x, y1, y2, foo] = greed[i];
ans[x][y1] = -1;
ans[x][y2] = -3;
sum += a[x][y1] + a[x][y2];
}
deque<pair<int, int>>dq;
for(int i = 0; i < k; i++){
dq.emplace_back(n >> 1, i);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(ans[i][j] == -3){
auto [u, v] = dq.front();
dq.pop_front();
if(u > 0){
dq.emplace_back(u - 1, v);
}
ans[i][j] = v;
}
}
}
for(int i = 0; i < n; i++){
vector<bool>use(k, false);
for(int j = 0; j < m; j++){
if(ans[i][j] > -1){
use[ans[i][j]] = true;
}
}
vector<int>I;
for(int j = 0; j < k; j++){
if(!use[j]){
I.emplace_back(j);
}
}
for(int j = 0; j < m; j++){
if(ans[i][j] == -2){
ans[i][j] = I.back();
I.pop_back();
}
}
}
allocate_tickets(ans);
return sum;
}
}
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();
}
if(k == m){
return sub4::solve();
}
return sub3567::solve();
}
