#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Pier {
int x, y;
ll fishL = 0, fishAct = 0, fishR = 0, val[2] = {0, 0};
};
struct Fish {
bool req;
int y;
ll pds;
};
const ll N = 1e5 + 42, INF = 1e15 + 42;
ll sz[N];
vector<Fish> fish[N];
vector<Pier> pier[N];
unordered_map<ll, ll> nb[N];
ll max_weights(int n, int M, vector<int> X, vector<int> Y, vector<int> W) {
for(int i = 0; i < M; i++) {
Y[i] += 1;
fish[X[i]].push_back({false, Y[i], W[i]});
for(int j = max(X[i]-2, 0); j < min(X[i]+3, n); j++)
fish[j].push_back({true, Y[i], 0});
pier[X[i]].push_back({X[i], Y[i]});
if(X[i] != 0)
pier[X[i]-1].push_back({X[i], Y[i]});
if(X[i] != n-1)
pier[X[i]+1].push_back({X[i], Y[i]});
}
for(int i = 0; i < n; i++) {
sort(fish[i].begin(), fish[i].end(),
[](Fish a, Fish b) {
if(a.y == b.y) {
if(a.req == b.req)
return false;
return b.req;
}
return a.y < b.y;
});
ll sum = 0;
for(Fish f : fish[i]) {
if(f.req) {
nb[i][f.y] = sum;
} else {
sum += f.pds;
}
}
}
for(int i = 0; i < n; i++) {
for(Pier& p : pier[i]) {
if(i != 0)
p.fishL = nb[i-1][p.y];
p.fishAct = nb[i][p.y];
if(i != n-1)
p.fishR = nb[i+1][p.y];
}
}
for(int i = 0; i < n; i++)
sort(pier[i].begin(), pier[i].end(),
[](Pier a, Pier b) {
return a.y < b.y;
});
for(int i = 0; i < n; i++)
sz[i] = (ll)pier[i].size();
ll maxi = 0;
for(int i = 0; i < n; i++) {
for(Pier& p : pier[i]) {
p.val[0] = maxi + p.fishL - p.fishAct;
p.val[1] = maxi + p.fishL + p.fishR;
}
ll id[2] = {0, 0}, maxiLL = -INF, maxiL = -INF;
for(Pier& p : pier[i]) {
if(i > 0) {
while(id[0] < sz[i-1] && pier[i-1][id[0]].y <= p.y) {
maxiL = max(maxiL, pier[i-1][id[0]].val[0]);
id[0]++;
}
}
if(i > 1) {
while(id[1] < sz[i-2] && pier[i-2][id[1]].y <= p.y) {
maxiLL = max(maxiLL, pier[i-2][id[1]].val[1] - pier[i-2][id[1]].fishR - pier[i-2][id[1]].fishAct);
id[1]++;
}
}
p.val[0] = max(p.val[0], max(maxiL, maxiLL) - p.fishAct + p.fishL);
p.val[1] = max(p.val[1], max(maxiL, maxiLL) + p.fishL + p.fishR);
}
if(i == 0) {
id[0] = id[1] = -1;
} else if(i == 1) {
id[0] = sz[i-1]-1;
id[1] = -1;
} else {
id[0] = sz[i-1]-1;
id[1] = sz[i-2]-1;
}
maxiLL = maxiL = -INF;
reverse(pier[i].begin(), pier[i].end());
for(Pier& p : pier[i]) {
if(i > 0) {
while(id[0] >= 0 && pier[i-1][id[0]].y >= p.y) {
maxiL = max(maxiL, pier[i-1][id[0]].val[1]);
id[0]--;
}
}
if(i > 1) {
while(id[1] >= 0 && pier[i-2][id[1]].y >= p.y) {
maxiLL = max(maxiLL, pier[i-2][id[1]].val[1]);
id[1]--;
}
}
p.val[0] = max(p.val[0], maxiLL - p.fishAct);
p.val[1] = max(p.val[1], max(maxiLL, maxiL - p.fishAct) + p.fishR);
}
reverse(pier[i].begin(), pier[i].end());
if(i > 1) {
for(Pier p : pier[i-2])
maxi = max(maxi, max(p.val[0], p.val[1]));
}
}
for(Pier p : pier[n-1])
maxi = max(maxi, max(p.val[0], p.val[1]));
for(Pier p : pier[n-2])
maxi = max(maxi, max(p.val[0], p.val[1]));
return maxi;
}
