#include "fish.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 1e5 + 10;
int n , m , sz[N];
vector <pair<int , int>> all[N];
vector <long long> dp[2][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 < n ; i++)
all[i].push_back({0 , 0});
for(int i = 0 ; i < m ; i++)
all[X[i]].push_back(make_pair(Y[i] , W[i]));
for(int i = 0 ; i < n ; i++)
all[i].push_back({n , 0});
for(int i = 0 ; i < n ; i++)
{
sort(all[i].begin() , all[i].end());
sz[i] = all[i].size();
dp[0][i].resize(sz[i] , 0);
dp[1][i].resize(sz[i] , 0);
}
long long ans = 0;
for(int i = 1 ; i < n ; i++)
{
long long mx = 0;
for(auto u : dp[0][i - 1])
mx = max(mx , u);
for(auto u : dp[1][i - 1])
mx = max(mx , u);
int pos = 0;
long long val_down = 0;
for(int j = 0 ; j < sz[i] ; j++)
{
while(pos != sz[i - 1] && all[i - 1][pos].F < all[i][j].F)
{
val_down = max(val_down , dp[0][i - 1][pos]);
val_down += all[i - 1][pos].S;
pos++;
}
dp[0][i][j] = max(dp[0][i][j] , (max(mx , val_down)));
dp[1][i][j] = max(dp[1][i][j] , (max(mx , val_down)));
}
long long val_up = 0;
pos = sz[i - 1] - 1;
for(int j = sz[i] - 1 ; j >= 0 ; j--)
{
while(pos >= 0 && all[i - 1][pos].F > all[i][j].F)
{
val_up = max(val_up , dp[1][i - 1][pos]);
pos--;
}
val_up += all[i][j].S;
dp[1][i][j] = max(dp[1][i][j] , val_up);
ans = max(ans , dp[1][i][j]);
ans = max(ans , dp[0][i][j]);
}
}
return ans;
}
