#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = (ll)1e9+7;
#define P pair
#define S second
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n=(int)x.size();
int m=(int)x[0].size();
int h=n/2;
V<V<int>>vp(n,V<int>(m));
V<int>left(n),right(n);
ll a=0;
for (int i=0;i<n;i++) {
if (i<h) {
for (int j=0;j<m;j++) {
vp[i][j]=-1;
}
left[i]=-1;
right[i]=m-k;
for (int j=m-1;j>=m-k;j--) {
a+=x[i][j];
vp[i][j]=1;
}
}
else {
for (int j=0;j<m;j++) {
vp[i][j]=-1;
}
right[i]=m;
left[i]=k-1;
for (int j=0;j<=k-1;j++) {
a-=x[i][j];
vp[i][j]=0;
}
}
}
multiset<P<int,int>>s1,s2;
for (int i=0;i<n;i++) {
if (right[i]!=m) {
s1.insert({-x[i][right[i]]-x[i][left[i]+1],i});
}
if (left[i]!=-1) {
s2.insert({x[i][left[i]]+x[i][right[i]-1],i});
}
}
while (true) {
V<ll>v(2,-1e17);
V<int>id(2,-1);
v[0]=prev(s1.end())->F;
v[1]=prev(s2.end())->F;
id[0]=prev(s1.end())->S;
id[1]=prev(s2.end())->S;
s1.erase(prev(s1.end()));
s2.erase(prev(s2.end()));
auto it=s2.find({x[id[0]][left[id[0]]]+x[id[0]][right[id[0]]-1],id[0]});
if (it!=s2.end()) {
s2.erase(it);
}
it=s1.find({-x[id[1]][right[id[1]]]-x[id[1]][left[id[1]]+1],id[1]});
if (it!=s1.end()) {
s1.erase(it);
}
if (v[0]+v[1]<=0) {
break;
}
a+=v[0]+v[1];
vp[id[0]][right[id[0]]]=-1;
vp[id[0]][left[id[0]]+1]=0;
vp[id[1]][left[id[1]]]=-1;
vp[id[1]][right[id[1]]-1]=1;
left[id[0]]++;
right[id[0]]++;
left[id[1]]--;
right[id[1]]--;
for (int j=0;j<2;j++) {
int i=id[j];
if (right[i]!=m) {
s1.insert({-x[i][right[i]]-x[i][left[i]+1],i});
}
if (left[i]!=-1) {
s2.insert({x[i][left[i]]+x[i][right[i]-1],i});
}
}
}
V<int>l;
for (int i=0;i<h;i++) {
for (int j=0;j<k;j++) {
l.pb(j);
}
}
V<V<int>>ans(n,V<int>(m,-1));
int id=0;
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
if (vp[i][j]==0) {
ans[i][j]=l[id];
id++;
}
}
}
for (int i=0;i<n;i++) {
set<int>st;
for (int j=0;j<k;j++) {
st.insert(j);
}
for (int j=0;j<m;j++) {
if (vp[i][j]==0) {
st.erase(ans[i][j]);
}
}
for (int j=0;j<m;j++) {
if (vp[i][j]==1) {
ans[i][j]=*st.begin();
st.erase(st.begin());
}
}
}
allocate_tickets(ans);
return a;
}
