#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for (int i = s; i <= e; ++i)
#define rrep(i,s,e) for (int i = s; i >= e; --i)
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size(), cnt[n] = {};
vector<vector<int>> answer(n, vi(m, -1));
if (k==m) {
ii vals[n*m];
rep (i,0,n-1) rep (j,0,m-1) vals[i*m+j] = {x[i][j], i};
sort(vals, vals+n*m);
ll tot = 0;
rep (i,0,n*m-1) {
if (i<n*m/2) {
tot -= vals[i].fi;
cnt[vals[i].se]++;
}
else tot += vals[i].fi;
}
int id = 0;
rep (i,0,n-1) {
rep (j,0,m-1) answer[i][j] = (id+j)%m;
id += cnt[i];
}
allocate_tickets(answer);
return tot;
}
ll dp[k*n/2+1][n+1] = {}, dp_took[k*n/2+1][n+1] = {};
rep (i,0,k*n/2) rep (j,0,n) dp[i][j] = -5e18;
dp[0][0] = 0;
rep (i,0,n-1) {
ll cur = 0;
rep (j,0,k-1) cur -= x[i][j];
rep (j,0,k) {
rep (s,0,k*n/2) {
if (j>s) continue;
if (dp[s-j][i]!=-5e18 && dp[s-j][i]+cur>dp[s][i+1]) {
dp[s][i+1] = dp[s-j][i] + cur;
dp_took[s][i+1] = j;
}
}
if (j==k) break;
cur += x[i][k-1-j] + x[i][m-1-j];
}
}
ll cur = k*n/2, day = 0;
rrep (i,n-1,0) {
ll num = dp_took[cur][i+1];
rep (j,0,k-1) answer[i][(m-num+j)%m] = (day+j)%k;
day += num;
cur -= num;
}
allocate_tickets(answer);
return dp[k*n/2][n];
}
