#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SZ(x) int(x.size())
#define maxs(a, b) (a = max(a, b))
const int MXN = 1e5+5;
const ll inf = 1e18;
vector<int> vec[MXN];
vector<ll> dp[3][MXN];
ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
for(int i=0; i<m; i++) vec[++X[i]].push_back(i);
Y.push_back(0);
W.push_back(0);
Y.push_back(n);
W.push_back(0);
for(int i=0; i<=n; i++) {
vec[i].push_back(m);
if(i) vec[i].push_back(m+1);
sort(vec[i].begin(), vec[i].end(), [&](int x, int y) {
return Y[x]<Y[y];
});
if(i) {
dp[0][i].resize(SZ(vec[i-1]), i==1 ? 0 : -inf);
for(int t : {1, 2})
dp[t][i].resize(SZ(vec[i]), i==1 ? 0 : -inf);
}
}
for(int i=2; i<=n; i++) {
maxs(dp[0][i][0], *max_element(dp[0][i-1].begin(), dp[0][i-1].end())); // .. 0 0
int ptr=0;
ll sum=0;
for(int j=0; j<SZ(vec[i-1]); j++) {
while(ptr<SZ(vec[i]) && Y[vec[i][ptr]]<Y[vec[i-1][j]])
sum += W[vec[i][ptr++]];
maxs(dp[0][i][j], max(dp[1][i-1][j], dp[2][i-1][j])+sum);
} // .. x 0
ptr = SZ(vec[i-2])-1;
ll mx = -inf;
for(int j=SZ(vec[i])-1; j>=0; j--) {
while(ptr>=0 && Y[vec[i-2][ptr]]>=Y[vec[i][j]])
maxs(mx, dp[0][i-1][ptr--]);
maxs(dp[1][i][j], mx);
maxs(dp[2][i][j], mx);
} // x 0 y (x>=y)
ptr=0, sum=0, mx = -inf;
int ptr2=0, ptr3=0;
ll sum2 = 0;
for(int j=0; j<SZ(vec[i]); j++) {
while(ptr<SZ(vec[i-2]) && Y[vec[i-2][ptr]]<=Y[vec[i][j]]) {
while(ptr2<SZ(vec[i-1]) && Y[vec[i-1][ptr2]]<Y[vec[i-2][ptr]])
sum2 += W[vec[i-1][ptr2++]];
maxs(mx, dp[0][i-1][ptr++]-sum2);
}
while(ptr3<SZ(vec[i-1]) && Y[vec[i-1][ptr3]]<Y[vec[i][j]])
sum += W[vec[i-1][ptr3++]];
maxs(dp[1][i][j], mx+sum);
maxs(dp[2][i][j], mx+sum);
} // x 0 y (x<=y)
ptr=0, sum=0;
ptr2=0;
mx = -inf, sum2=0;
for(int j=0; j<SZ(vec[i]); j++) {
while(ptr<SZ(vec[i-1]) && Y[vec[i-1][ptr]]<Y[vec[i][j]])
sum += W[vec[i-1][ptr++]];
while(ptr2<SZ(vec[i-1]) && Y[vec[i-1][ptr2]]<=Y[vec[i][j]]) {
maxs(mx, dp[1][i-1][ptr2]-sum2);
sum2 += W[vec[i-1][ptr2++]];
}
maxs(dp[1][i][j], mx+sum);
maxs(dp[2][i][j], mx+sum);
} // x y (x<=y)
ptr=SZ(vec[i-1])-1;
mx = -inf;
sum = 0;
ptr2=SZ(vec[i])-1;
sum2=0;
for(int j=SZ(vec[i])-1; j>=0; j--) {
while(ptr>=0 && Y[vec[i-1][ptr]]>=Y[vec[i][j]]) {
while(ptr2>=0 && Y[vec[i][ptr2]]>=Y[vec[i-1][ptr]])
sum2 += W[vec[i][ptr2--]];
maxs(mx, dp[2][i-1][ptr--]-sum2);
}
sum += W[vec[i][j]];
maxs(dp[2][i][j], mx+sum);
} // x y (x>=y)
}
return max({
*max_element(dp[0][n].begin(), dp[0][n].end()),
*max_element(dp[1][n].begin(), dp[1][n].end()),
*max_element(dp[2][n].begin(), dp[2][n].end())
});
}
