#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 12;
typedef long long ll;
int n,m;
vector<vector<vector<ll>>> dp(N);
vector<int> g[N],in[N],t[N];
map<int,int> a[N];
long long max_weights(int nn, int mm,vector<int> X, vector<int> Y,vector<int> W) {
n = nn;
m = mm;
for(int i = 0;i < m;i++) {
X[i]++;
Y[i]++;
g[X[i]].push_back(Y[i]);
a[X[i]][Y[i]] = W[i];
}
for(int i = 0;i <= n;i++) {
for(int j:g[i]) {
in[i].push_back(j - 1);
in[i].push_back(j);
}
for(int j:g[i+1]) {
in[i].push_back(j);
}
for(int j:g[i-1]) {
in[i].push_back(j);
}
in[i].push_back(0);
sort(in[i].begin(),in[i].end());
in[i].resize(unique(in[i].begin(),in[i].end()) - in[i].begin());
dp[i].resize((int)in[i].size());
for(int j = 0;j < (int)in[i].size();j++) {
t[i].push_back((a[i].count(in[i][j]) ? a[i][in[i][j]] : 0));
dp[i][j].resize(2);
}
}
//0 : L > R
//1 : L < R
for(int i = 2;i <= n;i++) {
int j1 = 0;
ll mx = -1e18,p_ = 0,_p = 0;
for(int j = 0;j < (int)in[i].size();j++) {
_p += a[i - 1][in[i][j]];
while(j1 < (int)in[i - 1].size() && in[i - 1][j1] <= in[i][j]) {
p_ += (a[i - 1].count(in[i - 1][j1]) ? a[i - 1][in[i - 1][j1]] : 0);
mx = max(mx,dp[i - 1][j1][1] - p_);
j1++;
}
dp[i][j][1] = max(dp[i - 1][0][0],_p + mx);
}
j1 = (int)in[i - 1].size() - 1;
mx = -1e18;
p_ = 0,_p = 0;
for(int j = (int)in[i].size() - 1;j >= 0;j--) {
while(j1 >= 0 && in[i - 1][j1] >= in[i][j]) {
mx = max(mx,max(dp[i - 1][j1][0],dp[i - 1][j1][1]) - _p);
_p += (a[i].count(in[i - 1][j1]) ? a[i][in[i - 1][j1]] : 0);
j1--;
}
dp[i][j][0] = p_ + mx;
p_ += t[i][j];
}
}
ll res = 0;
for(int i = 1;i <= n;i++) {
for(int j = 0;j < (int)in[i].size();j++) {
res = max({res,dp[i][j][0],dp[i][j][1]});
}
}
return res;
}
