// #include "A.cpp"
#include <bits/stdc++.h>
// #include <vector>
using namespace std;
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(x) cout << #x << " " << x << endl;
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define pb push_back
#define ld long double
#define ll long long
// #include "tickets.h"
// #include <vector>
void allocate_tickets(vector<vector<int>> a);
struct node {
long long i, j, value;
bool operator!=(const node& other) const {
return (other.i != i || other.j != j || other.value != value);
}
bool operator==(const node& other) const {
return (other.i == i && other.j == j && other.value == value);
}
bool operator<(const node& other) const {
if(value != other.value) {
return value < other.value;
}
return j < other.j;
}
};
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> answer;
// dbg(k)
if(m == 1) {
vector<vector<int>> answ;
long long pat = 0;
vector<long long> values;
map<long long, int> mp;
for(int i = 0; i < n; i++) {
answ.push_back({0});
values.push_back(x[i][0]);
mp[x[i][0]]++;
pat += x[i][0];
}
sort(all(values));
ll s = INT64_MAX, left = 0, leftCnt = 0;
for(auto i: mp) {
leftCnt += i.second;
left += i.second * i.first;
ll rightCnt = n - leftCnt;
pat -= i.second * i.first;
s = min(s, leftCnt * i.first - left + pat - rightCnt * i.first);
}
allocate_tickets(answ);
return s;
} else if(k == m) {
vector<node> all_members;
vector<deque<int>> plus_or_minus;
vector<int> poped_front(n);
plus_or_minus.resize(n);
answer.resize(n);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
//
plus_or_minus[i].resize(m);
answer[i].resize(m);
//
all_members.push_back({i, j, x[i][j]});
}
}
sort(all(all_members));
int mid = (n * m) / 2;
long long answ = 0;
for(int i = 0; i < n * m; i++) {
if(i < mid) {
plus_or_minus[all_members[i].i][all_members[i].j] = 0;
answ -= all_members[i].value;
} else {
plus_or_minus[all_members[i].i][all_members[i].j] = 1;
answ += all_members[i].value;
}
}
for(int i = 0; i < m; i++) {
int plus = n / 2, minus = n / 2;
vector<node> new_round;
vector<bool> vis(n);
for(int j = 0; j < n; j++) {
if(!vis[j] && plus && sz(plus_or_minus[j]) && plus_or_minus[j][0] == 1 && plus_or_minus[j].back() == 1) {
int k = plus_or_minus[j].size() - 1 + poped_front[j];
plus_or_minus[j].pop_back();
answer[j][k] = i, vis[j] = true;
plus--;
}
}
for(int j = 0; j < n; j++) {
if(!vis[j] && minus && sz(plus_or_minus[j]) && plus_or_minus[j][0] == 0 && plus_or_minus[j].back() == 0) {
int k = plus_or_minus[j].size() - 1 + poped_front[j];
plus_or_minus[j].pop_back();
answer[j][k] = i, vis[j] = true;
minus--;
}
}
for(int j = 0; j < n; j++) {
if(!vis[j] && plus && sz(plus_or_minus[j]) && plus_or_minus[j].back() == 1) {
int k = plus_or_minus[j].size() - 1 + poped_front[j];
plus_or_minus[j].pop_back();
answer[j][k] = i, vis[j] = true;
plus--;
} else if(!vis[j] && minus && sz(plus_or_minus[j]) && plus_or_minus[j][0] == 0) {
int k = poped_front[j];
plus_or_minus[j].pop_front();
answer[j][k] = i, vis[j] = true;
poped_front[j]++;
minus--;
}
}
assert(minus == 0 && plus == 0);
}
allocate_tickets(answer);
return answ;
} else {
vector<vector<node>> all;
for(int i = 0; i < n; i++) {
vector<node> row;
for(int j = 0; j < m; j++) {
row.push_back({i, j, x[i][j]});
}
sort(all(row));
all.push_back(row);
}
deque<deque<node>> last_n_k, first_k;
// dbg(sz(st))
for(int i = 0; i < n; i++) {
deque<node> curr_row, curr_st;
for(int j = 0; j < k; j++) {
curr_row.push_back(all[i][j]);
}
for(int j = k; j < m; j++) {
curr_st.push_back(all[i][j]);
}
first_k.push_back(curr_row);
last_n_k.push_back(curr_st);
}
// dbg((n * k) / 2)
priority_queue<pair<long long, int>, vector<pair<long long, int>>> candidates;
for(int j = 0; j < n; j++) {
if(first_k[j].empty()) continue;
candidates.push({first_k[j].back().value + last_n_k[j].back().value, j});
}
for(int i = 0; i < ((n * k) / 2); i++) {
int more_valuable = candidates.top().second;
candidates.pop();
node last = first_k[more_valuable].back();
last_n_k[more_valuable].pop_back();
first_k[more_valuable].pop_back();
last_n_k[more_valuable].push_front(last);
if(!first_k[more_valuable].empty() && !last_n_k[more_valuable].empty()) {
candidates.push({first_k[more_valuable].back().value + last_n_k[more_valuable].back().value, more_valuable});
}
}
int all_sz = 0;
for(int j = 0; j < n; j++) {
all_sz += sz(first_k[j]);
}
// assert(all_sz == ((n * k) / 2));
{
//
vector<node> all_members;
vector<deque<int>> plus_or_minus;
vector<int> poped_front(n);
map<pair<int, int>, pair<int, int>> mp;
plus_or_minus.resize(n);
answer.resize(n);
for(int i = 0; i < n; i++) {
//
plus_or_minus[i].resize(k);
answer[i].resize(k);
int curr_index = 0;
vector<long long> new_values;
for(int j = 0; j < sz(first_k[i]); j++) {
mp[{i, curr_index++}] = {all[i][j].i, all[i][j].j};
new_values.push_back(all[i][j].value);
}
int cnt = k - sz(first_k[i]);
for(int j = m - 1; cnt && j >= 0; j--, cnt--) {
mp[{i, curr_index++}] = {all[i][j].i, all[i][j].j};
new_values.push_back(all[i][j].value);
}
sort(all(new_values));
for(int j = 0; j < sz(new_values); j++) {
all_members.push_back({i, j, new_values[j]});
}
}
sort(all(all_members));
int mid = (n * k) / 2;
long long answ = 0;
for(int i = 0; i < n * k; i++) {
if(i < mid) {
plus_or_minus[all_members[i].i][all_members[i].j] = 0;
answ -= all_members[i].value;
} else {
plus_or_minus[all_members[i].i][all_members[i].j] = 1;
answ += all_members[i].value;
}
}
for(int i = 0; i < k; i++) {
int plus = n / 2, minus = n / 2;
vector<node> new_round;
vector<bool> vis(n + 1, false);
for(int j = 0; j < n; j++) {
if(!vis[j] && plus && sz(plus_or_minus[j]) && plus_or_minus[j][0] == 1 && plus_or_minus[j].back() == 1) {
int ki = plus_or_minus[j].size() - 1 + poped_front[j];
plus_or_minus[j].pop_back();
assert(ki < k);
answer[j][ki] = i, vis[j] = true;
plus--;
}
}
for(int j = 0; j < n; j++) {
if(!vis[j] && minus && sz(plus_or_minus[j]) && plus_or_minus[j][0] == 0 && plus_or_minus[j].back() == 0) {
int ki = plus_or_minus[j].size() - 1 + poped_front[j];
plus_or_minus[j].pop_back();
assert(ki < k);
answer[j][ki] = i, vis[j] = true;
minus--;
}
}
for(int j = 0; j < n; j++) {
if(!vis[j] && plus && sz(plus_or_minus[j]) && plus_or_minus[j].back() == 1) {
int ki = plus_or_minus[j].size() - 1 + poped_front[j];
plus_or_minus[j].pop_back();
assert(ki < k);
answer[j][ki] = i, vis[j] = true;
plus--;
} else if(!vis[j] && minus && sz(plus_or_minus[j]) && plus_or_minus[j][0] == 0) {
int ki = poped_front[j];
plus_or_minus[j].pop_front();
assert(ki < k);
answer[j][ki] = i, vis[j] = true;
poped_front[j]++;
minus--;
}
}
assert(minus == 0 && plus == 0);
}
vector<vector<int>> answii(n, vector<int> (m, -1));
for(int i = 0; i < sz(answer); i++) {
for(int j = 0; j < sz(answer[i]); j++) {
auto curr_pos = mp[{i, j}];
assert(curr_pos.first < n && curr_pos.second < m);
answii[curr_pos.first][curr_pos.second] = answer[i][j];
}
}
allocate_tickets(answii);
return answ;
}
}
//
allocate_tickets(answer);
return 1;
}
