#include "fish.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e5+5;
ll mx;
vector<vector<pair<ll, ll>>> v(nx), dp(nx), mx1(nx), mx2(nx), mx3(nx);
ll get_val(ll col, ll row)
{
return prev(upper_bound(v[col].begin(), v[col].end(), make_pair(row, LLONG_MAX)))->second;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
for (int i=0; i<M; i++) v[X[i]+1].push_back({Y[i]+1, W[i]});
for (int i=0; i<=N+1 ; i++) v[i].push_back({0, 0}), sort(v[i].begin(), v[i].end());
for (int i=1; i<=N; i++) for (int j=1; j<v[i].size(); j++) v[i][j].second+=v[i][j-1].second;
mx1[0].push_back({0, 0}); mx2[0].push_back({N, -1e18}); mx3[0].push_back({0, 0});
for (int i=1; i<=N; i++)
{
dp[i].push_back({0, 0});
for (int j=1; j<v[i-1].size(); j++) dp[i].push_back({v[i-1][j].first, 0ll});
for (int j=1; j<v[i+1].size(); j++) dp[i].push_back({v[i+1][j].first, 0ll});
sort(dp[i].begin(), dp[i].end());
for (int j=0; j<dp[i].size(); j++)
{
ll c=dp[i][j].first; dp[i][j].first=0;
dp[i][j].first=max(dp[i][j].first, get_val(i+1, c)+get_val(i-1, c)+(prev(upper_bound(mx1[i-1].begin(), mx1[i-1].end(), make_pair(c, LLONG_MAX))))->second);
dp[i][j].second=max(dp[i][j].second, get_val(i+1, c)-get_val(i, c)+(lower_bound(mx2[i-1].begin(), mx2[i-1].end(), make_pair(c, LLONG_MIN)))->second);
if (i>=2) dp[i][j].first=max(dp[i][j].first, get_val(i+1, c)+(lower_bound(mx2[i-2].begin(), mx2[i-2].end(), make_pair(c, LLONG_MIN)))->second);
if (i>=2) dp[i][j].first=max(dp[i][j].first, get_val(i+1, c)+get_val(i-1, c)+(prev(upper_bound(mx3[i-2].begin(), mx3[i-2].end(), make_pair(c, LLONG_MAX))))->second);
mx1[i].push_back({c, dp[i][j].first-get_val(i, c)-get_val(i+1, c)});
mx2[i].push_back({c, max(dp[i][j].first, dp[i][j].second)});
mx3[i].push_back({c, max(dp[i][j].first, dp[i][j].second)-get_val(i+1, c)});
//cout<<i<<' '<<c<<' '<<dp[i][j].first<<' '<<dp[i][j].second<<'\n';
mx=max({mx, dp[i][j].first, dp[i][j].second});
}
for (int j=1; j<mx1[i].size(); j++) mx1[i][j].second=max(mx1[i][j].second, mx1[i][j-1].second);
for (int j=mx1[i].size()-2; j>=0; j--) mx2[i][j].second=max(mx2[i][j].second, mx2[i][j+1].second);
for (int j=1; j<mx1[i].size(); j++) mx3[i][j].second=max(mx3[i][j].second, mx3[i][j-1].second);
mx2[i].push_back({N, -1e18});
}
return mx;
}
