#include "tickets.h"
#include "bits/stdc++.h"
#include <vector>
using namespace std;
typedef long long ll;
#define INF 100000000000007
typedef pair<int,int>pairll;
#define fr first
#define sc second
#define pb push_back
map<ll,ll>mp[1507];
vector<vector<int> >ans;
vector<vector<int> >v;
priority_queue<pairll>ql,qr,q;
ll res,l[1507],r[1507],n,m;
ll L(ll x){
if(l[x]==0)return -INF;
return v[x][r[x]]+v[x][l[x]-1];
}
ll R(ll x){
if(r[x]==m-1)return -INF;
return -v[x][l[x]]-v[x][r[x]+1];
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
n = x.size();
m = x[0].size();
if(k==m){
ll res=0;
for(int i=1;i<=n;i++){
vector<int>ro;
for(int j=0;j<m;j++){
res+=x[i-1][j];
ro.push_back(-1);
}
ans.push_back(ro);
q.push({-x[i-1][0],i});
}
//exit(1);
//cout<<q.size()<<endl;
for(int i=1;i<=(n*m)/2;i++){
//cout<<q.size()<<endl;
if(q.size()>0){
ll m1=q.top().fr;
ll m2=q.top().sc;
//cout<<m1<<" "<<m2<<" " <<rs[m2]<<endl;
l[m2]++;
q.pop();
res+=m1*2;
if(l[m2]<m)q.push({-x[m2-1][l[m2]],m2});
}
}
//cout<<q.size()<<endl;
//cout<<1<<endl;
ll g=0;
for(int i=n;i>=1;i--){
//cout<<i<<" "<<rs[i]<<endl;
ll h=g;
//cout<<i<<" "<<rs[i]<<endl;
for(int j=0;j<l[i];j++){
//cout<<j<<" "<<h<<endl;
ans[i-1][j]=(h%k);
h++;
//cout<<j<<" "<<h<<endl;
//cout<<j<<" ";
}
// cout<<endl;
g=h;
for(int j=m-1;j>=m-(k-l[i]);j--){
ans[i-1][j]=(h%k);
h++;
//cout<<j<<" "<<h<<endl;
//cout<<j<<" ";
}
//cout<<endl;
}
allocate_tickets(ans);
return res;
}
swap(v,x);
for(int i=0;i<n;i++){
vector<int>rs;
rs.clear();
for(int i=0;i<m;i++){
rs.pb(-1);
}
ans.pb(rs);
l[i]=(k+(i%2))/2;
r[i]=m-(k+(i+1)%2)/2-1;
for(int j=0;j<l[i];j++){
res-=v[i][j];
}
for(int j=r[i]+1;j<m;j++){
res+=v[i][j];
}
ql.push({L(i),i});
qr.push({R(i),i});
//cout<<i<<" "<<l[i]<<" "<<r[i]<<endl;
}
while(1){
while(ql.top().fr!=L(ql.top().sc))ql.pop();
while(qr.top().fr!=R(qr.top().sc))qr.pop();
ll m1=ql.top().sc;
ll m2=qr.top().sc;
if(L(m1)+R(m2)<=0)break;
ql.pop();
qr.pop();
if(m1==m2){
while(ql.top().fr!=L(ql.top().sc))ql.pop();
while(qr.top().fr!=R(qr.top().sc))qr.pop();
if(ql.size()==0 || qr.size()==0)break;
ll m3=ql.top().sc;
ll m4=qr.top().sc;
ql.pop();
qr.pop();
if(L(m3)+R(m2)<=0 && L(m1)+R(m4)<=0)break;
if(L(m3)+R(m2)>L(m1)+R(m4)){
res+=L(m3)+R(m2);
l[m3]--;
r[m3]--;
l[m2]++;
r[m2]++;
ql.push({L(m3),m3});
qr.push({R(m2),m2});
ql.push({L(m2),m2});
qr.push({R(m3),m3});
//ql.push({L(m1),m1});
qr.push({R(m4),m4});
}else{
res+=L(m1)+R(m4);
l[m1]--;
r[m1]--;
l[m4]++;
r[m4]++;
ql.push({L(m1),m1});
qr.push({R(m4),m4});
ql.push({L(m4),m4});
qr.push({R(m1),m1});
//ql.push({L(m1),m1});
ql.push({L(m3),m3});
}
}else{
res+=L(m1);
res+=R(m2);
l[m1]--;
r[m1]--;
l[m2]++;
r[m2]++;
ql.push({L(m1),m1});
qr.push({R(m2),m2});
ql.push({L(m2),m2});
qr.push({R(m1),m1});
}
}
ll g=0;
for(int i=n-1;i>=0;i--){
//cout<<i<<" "<<rs[i]<<endl;
ll h=g;
//cout<<i<<" "<<rs[i]<<endl;
for(int j=0;j<l[i];j++){
//cout<<j<<" "<<h<<endl;
ans[i][j]=(h%k);
h++;
//cout<<j<<" "<<h<<endl;
//cout<<j<<" ";
}
// cout<<endl;
g=h;
for(int j=m-1;j>=m-(k-l[i]);j--){
ans[i][j]=(h%k);
h++;
//cout<<j<<" "<<h<<endl;
//cout<<j<<" ";
}
//cout<<endl;
}
allocate_tickets(ans);
return res;
}
