#include"fish.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxN = 4e5+5;
vector<array<int,3>> v;
ll dp[mxN][2][2];
int N;
vector<vector<pair<ll,ll>>> pref;
ll pr(int x, ll y1, ll y2){ // [y1, y2[
auto z1 = prev(lower_bound(pref[x].begin(),pref[x].end(),make_pair(y1,-1ll)));
auto z2 = prev(lower_bound(pref[x].begin(),pref[x].end(),make_pair(y2,-1ll)));
return z2->second - z1->second;
}
ll nxt(int x, int y){
return lower_bound(v.begin(),v.end(),(array<int,3>){x+1,y,-1}) - v.begin();
}
ll f(int ind, int dir, int point){
if(~dp[ind][dir][point])return dp[ind][dir][point];
auto &d = dp[ind][dir][point] = 0;
auto z = nxt(v[ind][0],v[ind][1]);
if(dir == 1){
if(ind != N - 1 && v[ind][0] == v[ind+1][0])
d = max(d, f(ind+1,1,point) + point * (v[ind][0] ? pr(v[ind][0]-1, v[ind][1], v[ind+1][1]) : 0));
if(z != N)
d = max(d, f(z,1,1) + pr(v[ind][0], v[ind][1], v[z][1]));
}
else{
if(ind != 0 && v[ind][0] == v[ind-1][0])
d = max(d, f(ind-1,0,1) + v[ind-1][2]);
}
if(z != N && v[z][0] == v[z-1][0])
d = max(d, f(z-1,0,1) + v[z-1][2]);
auto z2 = nxt(v[ind][0]+1,v[ind][1]);
auto z3 = nxt(v[ind][0]+1,-5);
if(z3 != N)
d = max(d, f(z3,1,0) + pr(v[ind][0]+1,-2,v[ind][1]));
if(z2 != N)
d = max(d, f(z2,1,1) + pr(v[ind][0]+1,-2,v[z2][1]));
return d;
}
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){
memset(dp,-1,sizeof dp);
pref.resize(n,{{-5,0}});
for(int i = 0; i < m; ++i)v.push_back({x[i],y[i],w[i]});
for(int i = 0; i < n; ++i)v.push_back({i,n,0});
sort(v.begin(),v.end());
N = v.size();
for(int i = 0; i < N; ++i){
pref[v[i][0]].emplace_back(v[i][1], pref[v[i][0]].back().second + v[i][2]);
}
return f(0,1,1);
}
