#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 4e18;
vector<int> H[100100], A[100100];
vector<ll> dp[2][100100], S[100100], prf[2][100100], suf[2][100100];
int n, sz[100100];
ll cost(int i, int s, int e){
if (s>e || i==0) return 0;
int j1 = upper_bound(H[i].begin(), H[i].end(), s-1) - H[i].begin() - 1;
int j2 = upper_bound(H[i].begin(), H[i].end(), e) - H[i].begin() - 1;
return S[i][j2] - S[i][j1];
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
n = N;
for (int i=0;i<=N;i++) {H[i].push_back(0); H[i].push_back(N);}
for (int i=0;i<M;i++){
++X[i], ++Y[i];
H[X[i]].push_back(Y[i]);
H[X[i]].push_back(Y[i]-1);
if (X[i]>1) H[X[i]-1].push_back(Y[i]);
if (X[i]<N) H[X[i]+1].push_back(Y[i]);
}
for (int i=0;i<=N;i++){
sort(H[i].begin(), H[i].end());
H[i].erase(unique(H[i].begin(), H[i].end()), H[i].end());
sz[i] = H[i].size();
A[i].resize(sz[i], 0);
S[i].resize(sz[i], 0);
dp[0][i].resize(sz[i], 0);
dp[1][i].resize(sz[i], 0);
prf[0][i].resize(sz[i]);
prf[1][i].resize(sz[i]);
suf[0][i].resize(sz[i]);
suf[1][i].resize(sz[i]);
}
for (int i=0;i<M;i++){
int idx = lower_bound(H[X[i]].begin(), H[X[i]].end(), Y[i]) - H[X[i]].begin();
assert(idx < sz[X[i]]);
A[X[i]][idx] = W[i];
}
for (int i=1;i<=n;i++){
for (int j=1;j<sz[i];j++) S[i][j] = S[i][j-1] + A[i][j];
}
dp[0][0][0] = 0;
dp[1][0][0] = 0;
assert(sz[0]==2);
dp[0][0][1] = -INF;
dp[1][0][1] = -INF;
for (int i=1;i<=n;i++){
--i;
for (int j=0;j<sz[i];j++){
prf[0][i][j] = dp[0][i][j] + cost(i, H[i][j]+1, n);
prf[1][i][j] = max(dp[0][i][j], dp[1][i][j]);
if (j==0) continue;
prf[0][i][j] = max(prf[0][i][j], prf[0][i][j-1]);
prf[1][i][j] = max(prf[1][i][j], prf[1][i][j-1]);
}
for (int j=sz[i]-1;j>=0;j--){
ll X = cost(i+1, 1, H[i][j]);
suf[0][i][j] = max(dp[0][i][j], dp[1][i][j]) + X;
suf[1][i][j] = dp[1][i][j] + X;
if (j==sz[i]-1) continue;
suf[0][i][j] = max(suf[0][i][j], suf[0][i][j+1]);
suf[1][i][j] = max(suf[1][i][j], suf[1][i][j+1]);
}
++i;
for (int j=0;j<sz[i];j++){
ll X1 = cost(i-1, 1, H[i][j]);
ll X2 = cost(i, 1, H[i][j]);
///0 -> 0
int idx00 = upper_bound(H[i-1].begin(), H[i-1].end(), H[i][j]) - H[i-1].begin() - 1;
dp[0][i][j] = max(dp[0][i][j], prf[0][i-1][idx00] - (S[i-1].back() - X1));
///1 -> 0
if (i>=2){
int idx10 = upper_bound(H[i-2].begin(), H[i-2].end(), H[i][j]) - H[i-2].begin() - 1;
dp[0][i][j] = max(dp[0][i][j], prf[1][i-2][idx10] + X1);
if (idx10+1 < sz[i-2]) dp[0][i][j] = max(dp[0][i][j], suf[0][i-2][idx10+1]);
}
///0 -> 1
dp[1][i][j] = max(dp[1][i][j], dp[0][i-1][sz[i-1]-1] + (S[i].back() - X2));
///1 -> 1
int idx11 = idx00;
if (H[i-1][idx11]<H[i][j]) idx11++;
dp[1][i][j] = max(dp[1][i][j], suf[1][i-1][idx11] - X2);
}
}
return max(*max_element(dp[0][n].begin(), dp[0][n].end()), *max_element(dp[1][n].begin(), dp[1][n].end()));
}
