#include <bits/stdc++.h>
using namespace std;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
typedef long long ll;
#include "fish.h"
vector<vector<ll>> dp;
vector<int> X,Y;
int N,M;
vector<vector<ll>> pref;
vector<vector<int>> ind;
vector<vector<int>> pos;
ll query(int x, int l, int r){
if (pos[x].back()<l) return 0ll;
if (pos[x][0]>r) return 0ll;
if (l>r) return 0ll;
auto itl = lower_bound(pos[x].begin(), pos[x].end(), l);
auto itr = lower_bound(pos[x].begin(), pos[x].end(), r+1);
itr--;
ll hueh = 0;
if (itl!=pos[x].begin()){
itl--;
hueh = pref[x][(itl-pos[x].begin())];
}
return pref[x][(itr-pos[x].begin())]-hueh;
}
int getup(int node){
int xv = X[node];
int yv = Y[node];
return ind[xv][lower_bound(pos[xv].begin(), pos[xv].end(), yv+1)-pos[xv].begin()];
}
int getdown(int node){
int xv = X[node];
int yv = Y[node];
return ind[xv][lower_bound(pos[xv].begin(), pos[xv].end(), yv)-pos[xv].begin()-1];
}
int getnextup(int node){
int xv = X[node];
int yv = Y[node];
return ind[xv+1][lower_bound(pos[xv+1].begin(), pos[xv+1].end(), yv)-pos[xv+1].begin()];
}
int getnextdown(int node){
int xv = X[node];
int yv = Y[node];
return ind[xv+1][lower_bound(pos[xv+1].begin(), pos[xv+1].end(), yv+1)-pos[xv+1].begin()-1];
}
long long f(int node, int flag){
int x = X[node];
int y = Y[node];
//cout<<x<<" "<<y<<" "<<flag<<endl;
if (dp[node][flag]!=-1) return dp[node][flag];
if (flag==1){
dp[node][flag]=0;
if (y<N){
ll crr = 0;
int next = getup(node);
if (x>0) crr = query(x-1,y,Y[next]-1);
dp[node][flag]=crr+f(getup(node),1);
}
if (x+1<N){
int next = getnextup(node);
ll crr = query(x,y,Y[next]-1);
dp[node][flag]=max(dp[node][flag],crr+f(next,1));
next=getnextdown(node);
crr = query(x+1,Y[next],y-1);
dp[node][flag]=max(dp[node][flag],crr+f(next,0));
}
}
else if (flag==0){
dp[node][flag]=0;
if (y-1>=0){
int next = getdown(node);
dp[node][flag]=query(x,Y[next],y-1)+f(next,0);
}
if (x+1<N){
dp[node][flag]=max(dp[node][flag],f(getnextup(node),0));
if (y==0){
dp[node][flag]=max(dp[node][flag],f(M+x+1,2));
}
}
}
else {
dp[node][flag]=0;
if (y<N){
dp[node][flag]=f(getup(node),2);
}
if (x+1<N){
int next = getnextup(node);
ll crr = query(x,y,Y[next]-1);
dp[node][flag]=max(dp[node][flag],crr+f(next,1));
next=getnextdown(node);
crr = query(x+1,Y[next],y-1);
dp[node][flag]=max(dp[node][flag],crr+f(next,0));
}
}
if (flag!=0 && x+2<N){
dp[node][flag]=max(dp[node][flag],f(M+x+2,1));
}
//cout<<x<<" "<<y<<" "<<flag<<" "<<dp[node][flag]<<endl;
return dp[node][flag];
};
long long max_weights(int _N, int _M, std::vector<int> _X, std::vector<int> _Y, std::vector<int> _W) {
vector<vector<pair<int,pair<ll,int>>>> arr;
N=_N;
vector<int> W;
arr.resize(N);
vector<int> bb(N,0);
for (int i = 0; i < _Y.size(); ++i)
{
if (_Y[i]==0) bb[_X[i]]=_W[i];
else {
X.push_back(_X[i]);
Y.push_back(_Y[i]);
W.push_back(_W[i]);
M++;
}
}
for (int i = 0; i < N; ++i)
{
X.push_back(i);
Y.push_back(0);
W.push_back(bb[i]);
}
for (int i = 0; i < N; i++){
X.push_back(i);
Y.push_back(N);
W.push_back(0);
}
for (int i = 0; i < Y.size(); i++){
arr[X[i]].push_back({Y[i],{W[i],i}});
}
pref.resize(arr.size());
pos.resize(arr.size());
ind.resize(arr.size());
for (int i = 0; i < N; ++i)
{
sort(arr[i].begin(), arr[i].end());
pref[i].resize(arr[i].size());
pos[i].resize(arr[i].size());
ind[i].resize(arr[i].size());
for (int j = 0; j < arr[i].size(); j++){
pref[i][j]=arr[i][j].second.first;
if (j) pref[i][j]+=pref[i][j-1];
pos[i][j]=arr[i][j].first;
ind[i][j]=arr[i][j].second.second;
}
}
//0 decreasing
//1 increasing
//2 increasing, \
but forbidden to profit from back
//coutarr(X);
//coutarr(Y);
//coutarr(W);
//cout<<M<<endl;
dp.resize(Y.size(),vector<ll>(3,-1));
return f(M,2);
}
