#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MXN = 2e5 + 5;
long long mx[MXN];
vector<long long> lft[MXN], rig[MXN], in[MXN];
vector<long long> pre[2][MXN], suf[2][MXN];
vector<long long> dp[2][MXN];
vector<long long> ind[MXN];
vector<array<long long, 2>> val[MXN];
/*
0 = len[i] < len[i + 1];
1 = len[i] > len[i + 1];
*/
long long max_weights(int32_t N, int32_t M, vector<int32_t> X, vector<int32_t> Y, vector<int32_t> W)
{
for (int i = 0; i < M; i++)
{
X[i]++, Y[i]++;
if (X[i] - 1 >= 1) ind[X[i] - 1].push_back(Y[i]);
if (X[i] + 1 <= N) ind[X[i] + 1].push_back(Y[i]);
val[X[i]].push_back({Y[i], W[i]});
}
for (int i = 1; i <= N; i++)
{
sort(ind[i].begin(), ind[i].end());
ind[i].resize(unique(ind[i].begin(), ind[i].end()) - ind[i].begin());
sort(val[i].begin(), val[i].end());
}
for (int i = 1; i <= N; i++)
{
int k1 = 0, k2 = 0, k3 = 0;
for (int j = 0; j < ind[i].size(); j++)
{
lft[i].push_back((lft[i].empty() ? 0LL : lft[i].back()));
rig[i].push_back((rig[i].empty() ? 0LL : rig[i].back()));
in[i].push_back((in[i].empty() ? 0LL : in[i].back()));
while (k1 < val[i - 1].size() && val[i - 1][k1][0] <= ind[i][j]) lft[i][j] += val[i - 1][k1][1], k1++;
while (k2 < val[i + 1].size() && val[i + 1][k2][0] <= ind[i][j]) rig[i][j] += val[i + 1][k2][1], k2++;
while (k3 < val[i].size() && val[i][k3][0] <= ind[i][j]) in[i][j] += val[i][k3][1], k3++;
}
}
for (int i = 1; i <= N; i++)
{
int k1 = 0, k2 = 0, k3 = 0, k4 = 0;
for (int j = 0; j < ind[i].size(); j++)
{
dp[0][i].push_back(lft[i][j] + rig[i][j]);
dp[1][i].push_back(lft[i][j] + rig[i][j]);
if (i <= 1) continue;
while (k1 < ind[i - 1].size() && ind[i - 1][k1] <= ind[i][j]) k1++;
while (k2 < ind[i - 1].size() && ind[i - 1][k2] < ind[i][j]) k2++;
dp[0][i][j] = max(dp[0][i][j], (k1 - 1 >= 0 ? pre[0][i - 1][k1 - 1] : 0) + (lft[i][j] + rig[i][j]));
dp[1][i][j] = max(dp[1][i][j], (k2 < ind[i - 1].size() ? suf[0][i - 1][k2] : 0) + (rig[i][j] - in[i][j]));
if (i <= 2) continue;
while (k3 < ind[i - 2].size() && ind[i - 2][k3] <= ind[i][j]) k3++;
while (k4 < ind[i - 2].size() && ind[i - 2][k4] < ind[i][j]) k4++;
long long A = (k3 - 1 >= 0 ? pre[1][i - 2][k3 - 1] : 0) + lft[i][j] + rig[i][j];
long long B = (k4 < ind[i - 2].size() ? suf[1][i - 2][k4] : 0) + rig[i][j];
dp[0][i][j] = max({dp[0][i][j], A, B});
dp[1][i][j] = max({dp[1][i][j], A, B});
if (i <= 3) continue;
dp[0][i][j] = max(dp[0][i][j], mx[i - 3] + lft[i][j] + rig[i][j]);
dp[1][i][j] = max(dp[1][i][j], mx[i - 3] + lft[i][j] + rig[i][j]);
}
for (int j = 0; j < ind[i].size(); j++)
{
dp[1][i][j] = max(dp[1][i][j], dp[0][i][j]);
mx[i] = max({mx[i], dp[0][i][j], dp[1][i][j]});
}
for (int j = 0; j < ind[i].size(); j++)
{
pre[0][i].push_back(max((pre[0][i].empty() ? 0LL : pre[0][i].back()), dp[0][i][j] - rig[i][j] - in[i][j]));
pre[1][i].push_back(max((pre[1][i].empty() ? 0LL : pre[1][i].back()), max(dp[0][i][j], dp[1][i][j]) - rig[i][j]));
}
suf[0][i].assign(ind[i].size(), 0);
suf[1][i].assign(ind[i].size(), 0);
for (int j = (int)ind[i].size() - 1; j >= 0; j--)
{
if (j + 1 < ind[i].size()) suf[0][i][j] = suf[0][i][j + 1], suf[1][i][j] = suf[1][i][j + 1];
suf[0][i][j] = max(suf[0][i][j], dp[1][i][j]);
suf[1][i][j] = max(suf[1][i][j], max(dp[0][i][j], dp[1][i][j]));
}
mx[i] = max(mx[i], mx[i - 1]);
}
long long ans = 0;
for (int i = 1; i <= N; i++)
{
for (long long &j : dp[0][i]) ans = max(ans, j);
for (long long &j : dp[1][i]) ans = max(ans, j);
}
return ans;
}
