#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e16;
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
vector<vector<pair<ll, ll>>> p(n);
vector<int> len[n];
for(int i = 0; i < m; ++i) {
p[x[i]].push_back({y[i], w[i]});
len[x[i]].push_back(y[i]);
}
for(int i = 0; i < n; ++i) {
sort(p[i].begin(), p[i].end());
ll sum = 0;
for(int j = 0; j < p[i].size(); ++j) {
sum += p[i][j].second;
p[i][j].second = sum;
}
p[i].insert(p[i].begin(), make_pair(-1, 0));
}
for(int i = 0; i < n; ++i) {
len[i].push_back(n);
len[i].push_back(0);
sort(len[i].begin(), len[i].end());
len[i].erase(unique(len[i].begin(), len[i].end()), len[i].end());
}
map<ll, ll> dp[n + 1][2];
for(int i = 0; i <= n; ++i) {
dp[0][0][i] = dp[0][1][i] = 0;
}
//0 - increasing, 1 - decreasing
for(int i = 1; i < n; ++i) {
vector<pair<ll, ll>> mx0, mx1;
for(ll lastlen: len[i - 1]) {
dp[i][0][0] = max({dp[i][0][0], dp[i - 1][0][lastlen], dp[i - 1][1][lastlen]});
dp[i][1][0] = max({dp[i][1][0], dp[i - 1][0][lastlen], dp[i - 1][1][lastlen]});
ll cur = 0;
if(!mx0.empty()) cur = mx0.back().second;
auto paiu = upper_bound(p[i - 1].begin(), p[i - 1].end(), make_pair(lastlen - 1, LLONG_MAX)); --paiu;
cur = max(cur, dp[i - 1][0][lastlen] - paiu->second);
mx0.push_back({lastlen, cur});
}
reverse(len[i - 1].begin(), len[i - 1].end());
for(ll lastlen: len[i - 1]) {
ll cur = 0;
if(!mx1.empty()) cur = mx1.back().second;
auto paiu = upper_bound(p[i].begin(), p[i].end(), make_pair(lastlen - 1, LLONG_MAX)); --paiu;
cur = max(cur, dp[i - 1][0][lastlen] + paiu->second);
cur = max(cur, dp[i - 1][1][lastlen] + paiu->second);
mx1.push_back({lastlen, cur});
}
reverse(mx1.begin(), mx1.end());
for(ll curlen: len[i]) {
auto it1 = upper_bound(mx0.begin(), mx0.end(), make_pair(curlen, LLONG_MAX));
assert(it1 != mx0.begin()); --it1;
auto it2 = lower_bound(mx1.begin(), mx1.end(), make_pair(curlen, LLONG_MIN));
assert(it2 != mx1.end());
auto paiu = upper_bound(p[i - 1].begin(), p[i - 1].end(), make_pair(curlen - 1, LLONG_MAX)); --paiu;
dp[i][0][curlen] = max(dp[i][0][curlen], paiu->second + it1->second);
auto paiu2 = upper_bound(p[i].begin(), p[i].end(), make_pair(curlen - 1, LLONG_MAX)); --paiu2;
dp[i][1][curlen] = max(dp[i][1][curlen], it2->second - paiu2->second);
}
}
ll ans = 0;
for(int i = 0; i <= n; ++i) {
ans = max({ans, dp[n - 1][0][i], dp[n - 1][1][i]});
}
return ans;
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
