#include <bits/stdc++.h>
#include "tickets.h"
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ar array
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(s) (int) (s).size()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define ff(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define FF(i, a, b) for (int i = (int)(a); i >= (int)(b); --i)
#define trav(a, x) for (auto& (a) : (x))
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
int c, k, s;
int count_lower(vi x, int tar) {
int l = -1, r = sz(x);
while (r - l > 1) {
int m = l + r >> 1;
if (x[m] < tar) l = m;
else r = m;
}
return r;
}
int cnt;
int get_median(vvi a) {
int l = -1, r = (int) 2e9, tar = -1, big = 0, small = 0;
while (r - l > 1) {
small = big = 0;
tar = l + (r - l) / 2;
forn(i, sz(a)) {
small += count_lower(a[i], tar);
big += count_lower(a[i], tar + 1);
}
if (small > c * k / 2) r = tar;
else if (big < c * k / 2) l = tar;
else break;
}
cnt = small;
return tar;
}
i64 find_maximum(int _k, vvi d) {
k = _k, c = sz(d), s = sz(d[0]);
vvi sums = vvi(c, vi(k));
forn(i, c) forn(j, k) sums[i][j] = d[i][j] + d[i][s - k + j];
int median = get_median(sums);
i64 ans = 0;
int minus = 0, plus = c * k - 1;
vvi ret = vvi(c, vi(s));
forn(i, c) {
int j = 0;
for(; j < k && sums[i][j] < median; j++) {
ret[i][j] = minus % k;
minus++;
ans -= d[i][j];
}
for(; j < k && sums[i][j] == median && cnt < c * k / 2; j++) {
ret[i][j] = minus % k;
minus++; cnt++;
ans -= d[i][j];
}
ff(l, j, s - k + j - 1) ret[i][l] -= 1;
ff(l, s - k + j, s - 1) {
ret[i][j] = plus % k;
plus--;
ans += d[i][j];
}
}
allocate_tickets(ret);
return ans;
}
