#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 2e5 + 2;
map <int64, int64> dp [maxn][2];
int64 mx [maxn];
vector <pair <int64, int64> > p[maxn];
vector <pair <int64, int64> > pref [maxn], suff[maxn];
vector <int64> pos [maxn];
int64 psum (int64 i, int64 j) {
auto it = lower_bound(p[i].begin(), p[i].end(), make_pair(j, (int64) 1e18));
if (it == p[i].begin()) return 0;
return (--it)->second;
}
int64 max_weights(int n, int m, vector<int> x, vector<int> y,
vector<int> w) {
for (int i = 0; i < m; i++) {
pos[++x[i]].push_back(++y[i]);
p[x[i]].push_back({y[i], w[i]});
}
for (int i = 1; i <= n; i++){
sort(p[i].begin(), p[i].end());
sort(pos[i].begin(), pos[i].end());
int64 sum = 0;
for (auto& [j, c]: p[i]) {
int64 t = sum;
sum+=c;
c+=t;
}
}
for (int i = 1; i <= n; i++){
vector <int64> ps = {0, n};
for (auto j: pos[i-1]) ps.push_back(j);
for (auto j: pos[i+1]) ps.push_back(j);
sort(ps.begin(), ps.end());
for (auto j: ps){
auto it = lower_bound(suff[i-1].begin(), suff[i-1].end(), make_pair(j, -1ll));
dp[i][j][0] = -psum(i, j);
if (it != suff[i-1].end()) dp[i][j][0] += it->second;
it = lower_bound(pref[i - 1].begin(), pref[i - 1].end(), make_pair(j, (int64) 1e18));
dp[i][j][1] = ((i - 2 >= 0) ? mx[i-2]: 0) + psum(i-1, j);
if (it != pref[i-1].begin()) dp[i][j][1] = max(dp[i][j][1], (--it)->second + psum(i-1, j));
mx[i] = max({mx[i], dp[i][j][0], dp[i][j][1]});
}
for (auto j: ps) {
pref[i].push_back(make_pair(j, max((pref[i].empty() ? 0ll: pref[i].back().second), dp[i][j][1] - psum(i, j))));
}
reverse(ps.begin(), ps.end());
for (auto j: ps) {
suff[i].push_back(make_pair(j, max((suff[i].empty() ? 0ll: suff[i].back().second), max(dp[i][j][0], dp[i][j][1]) + psum(i + 1, j))));
}
reverse(suff[i].begin(), suff[i].end());
}
return mx[n];
}
