#include "bits/stdc++.h"
#include "tickets.h"
#define pb push_back
using namespace std;
const long long inf = 1e15;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> ans(n, vector<int>(m, -1));
if(m == 1){
long long val = 0;
vector<int> arr;
for(int i = 0; i < n; i++){
arr.pb(x[i][0]);
val += x[i][0];
ans[i][0] = 0;
}
sort(arr.begin(), arr.end());
for(int i = 0; i < n/2; i++){
val -= arr[i] * 2;
}
allocate_tickets(ans);
return val;
}
else if(k == 1){
vector<int> mini(n), maxi(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(x[i][j] > x[i][maxi[i]]){
maxi[i] = j;
}
if(x[i][j] < x[i][mini[i]]){
mini[i] = j;
}
}
}
vector<vector<long long> > dp(n+1, vector<long long>(n/2+2, -inf));
vector<vector<pair<int, int> > > par(n+1, vector<pair<int, int> >(n/2+2));
dp[0][0] = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j <= min(i, n/2); j++){
if(dp[i][j] + x[i][maxi[i]] > dp[i+1][j+1]){
dp[i+1][j+1] = dp[i][j] + x[i][maxi[i]];
par[i+1][j+1] = {i, j};
}
if(dp[i][j] - x[i][mini[i]] > dp[i+1][j]){
dp[i+1][j] = dp[i][j] - x[i][mini[i]];
par[i+1][j] = {i, j};
}
}
}
pair<int, int> now = {n, n/2};
while(now != make_pair(0, 0)){
pair<int, int> nxt = par[now.first][now.second];
if(now.second == nxt.second){
ans[nxt.first][mini[nxt.first]] = 0;
}
else{
ans[nxt.first][maxi[nxt.first]] = 0;
}
now = nxt;
}
allocate_tickets(ans);
return dp[n][n/2];
}
vector<vector<long long> > dp(n+1, vector<long long>(n*k/2 + 2, -inf));
vector<vector<pair<int, int> > > par(n+1, vector<pair<int, int> >(n*k/2+2));
dp[0][0] = 0;
for(int i = 0; i < n; i++){
vector<pair<int, int> > arr;
for(int j = 0; j < m; j++){
arr.pb({x[i][j], j});
}
sort(arr.begin(), arr.end());
vector<long long> add(k+1);
long long now = 0;
for(int j = 0; j <= k; j++){
now -= arr[j].first;
}
add[0] = now;
for(int j = 0; j < k; j++){
now += arr[(k - j)].first;
now += arr[m - j - 1].first;
add[j+1] = now;
}
for(int take = 0; take <= k; take++){
for(int j = 0; j + take <= n*k/2; j++){
if(dp[i+1][j + take] < dp[i][j] + add[take]){
dp[i+1][j + take] = dp[i][j] + add[take];
par[i+1][j + take] = {i, j};
}
}
}
}
int lstsm = 0, lstbg = k-1;
pair<int, int> now = {n, n*k/2};
while(now != make_pair(0, 0)){
pair<int, int> nxt = par[now.first][now.second];
int big = now.second - nxt.second;
int small = k - big;
vector<pair<int, int> > arr;
for(int j = 0; j < m; j++){
arr.pb({x[nxt.first][j], j});
}
sort(arr.begin(), arr.end());
for(int i = 0; i < small; i++){
ans[nxt.first][arr[i].second] = lstsm++;
if(lstsm == k) lstsm -= k;
}
for(int i = m-1; i >= m-big; i--){
ans[nxt.first][arr[i].second] = lstbg--;
if(lstbg == -1) lstbg += k;
}
now = nxt;
}
allocate_tickets(ans);
return dp[n][n*k/2];
}
