#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;
// cout << i << " " << j << " " << c << "\n";
}
}
// cout << "> " << psum(1, 3) << " " << psum(1, 5) << " " << psum(1, 2) << "\n";
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;
// dp[i][j][0] = suff[i-1][j] - p[i][j];
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].begin()) dp[i][j][1] = max(dp[i][j][1], (--it)->second + psum(i-1, j));
// dp[i][j][1] = max(mx[i-2] + p[i-1][j], pref[i-1][j] + p[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(pos[i].begin(), pos[i].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());
// for (int j = 0; j <= n; j++){
// pref[i][j] = max((j != 0 ? pref[i][j - 1]: 0ll), dp[i][j][1] - p[i][j]);
// }
// for (int j = n; j >= 0; j--){
// suff[i][j] = max((j != n ? suff[i][j + 1] : 0ll), max(dp[i][j][0], dp[i][j][1]) + p[i + 1][j]);
// }
}
return mx[n];
}
