#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef int32_t ii;
typedef long long ll;
#define int ll
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
const int INF = 1e18;
int max_weights(ii n, ii m, vector<ii> x, vector<ii> y, vector<ii> w) {
vector<vector<ar<int, 2>>> a(n + 1);
for(int i=0;i<m;i++){
x[i]++, y[i]++;
for(int t=-1;t<2;t++){
if(0 < x[i] + t && x[i] + t <= n){
a[x[i] + t].push_back({y[i], (t == 0) * w[i]});
}
}
}
vector<vector<ar<int, 2>>> dp(n + 1);
vector<vector<int>> pref(n + 2);
vector<vector<int>> tp(n + 1);
for(int i=0;i<=n;i++){
a[i].push_back({0, 0});
sort(a[i].begin(), a[i].end());
vector<ar<int, 2>> b;
for(auto [x, w] : a[i]){
if(b.empty() || b.back()[0] != x) b.push_back({x, 0});
b.back()[1] += w;
}
swap(a[i], b);
pref[i].resize(a[i].size());
dp[i].resize(a[i].size());
tp[i].resize(a[i].size());
for(int j=1;j<(int)pref[i].size();j++){
pref[i][j] = pref[i][j-1] + a[i][j][1];
}
}
//~ auto low = [&](int i, int j){
//~ int p = upper_bound(a[i].begin(), a[i].end(), (ar<int, 2>){j, INF}) - a[i].begin();
//~ return p - 1;
//~ };
//~ auto upp = [&](int i, int j){
//~ int p = lower_bound(a[i].begin(), a[i].end(), (ar<int, 2>){j, 0ll}) - a[i].begin();
//~ return p - 1;
//~ };
vector<int> pref_tp, suff_tp, pref_00, suff_11, suff_01;
{
pref_tp.resize(a[1].size());
pref_00.resize(a[1].size());
suff_tp.resize(a[1].size());
suff_01.resize(a[1].size());
suff_11.resize(a[1].size());
}
vector<int> mx(n + 1);
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
for(int i=1;i<=n;i++){
int j_ = 0;
for(int j=1;j<(int)a[i].size();j++){ // int j_ = a[i][j][0];
while(j_ + 1 < (int)a[i - 1].size() && a[i - 1][j_ + 1][0] <= a[i][j][0]) j_++;
dp[i][j][0] = pref[i - 1][j_];
if(3 <= i) dp[i][j][0] += mx[i - 3];
if(i > 1){
dp[i][j][0] = max(dp[i][j][0], pref_00[j] + pref[i - 1][j_]);
dp[i][j][1] = max(dp[i][j][1], suff_11[j] - pref[i][j]);
dp[i][j][1] = max(dp[i][j][1], suff_01[j] - pref[i][j]);
}
if(i > 2){
dp[i][j][0] = max(dp[i][j][0], pref_tp[j] + pref[i - 1][j_]);
dp[i][j][0] = max(dp[i][j][0], suff_tp[j]);
}
tp[i][j] = max(dp[i][j][0], dp[i][j][1]);
mx[i] = max(mx[i], tp[i][j]);
}
//~ cout<<"here"<<endl;
if(i < n){
pref_00.resize(a[i + 1].size());
pref_tp.resize(a[i + 1].size());
suff_tp.resize(a[i + 1].size() + 1);
suff_11.resize(a[i + 1].size() + 1);
suff_01.resize(a[i + 1].size() + 1);
int j_ = 1;
for(int j=1;j<(int)a[i + 1].size();j++){
pref_00[j] = pref_00[j - 1];
while(j_ < (int)a[i].size() && a[i][j_][0] <= a[i + 1][j][0]){
pref_00[j] = max(pref_00[j], dp[i][j_][0] - pref[i][j_]);
j_++;
}
//~ pref_00[j] = max(pref_00[j], dp[i][j][0] - pref[i][j]);
}
{
int j_ = (int)a[i].size() - 1, _j = (int)a[i + 1].size() - 1;
for(int j=_j;j>0;j--){
suff_11[j] = suff_11[j + 1];
while(j_ >= 0 && a[i][j_][0] > a[i + 1][j][0]){
while(a[i][j_][0] < a[i + 1][_j][0]) _j--;
suff_11[j] = max(suff_11[j], dp[i][j_][1] + pref[i + 1][_j]);
j_--;
}
while(a[i][j_][0] < a[i + 1][_j][0]) _j--;
suff_11[j] = max(suff_11[j], dp[i][j_][1] + pref[i + 1][_j]);
}
j_ = (int)a[i].size() - 1, _j = (int)a[i + 1].size() - 1;
for(int j=_j;j>0;j--){
suff_01[j] = suff_01[j + 1];
while(j_ >= 0 && a[i][j_][0] > a[i + 1][j][0] + 1){
while(a[i][j_][0] < a[i + 1][_j][0]) _j--;
suff_01[j] = max(suff_01[j], dp[i][j_][0] + pref[i + 1][_j]);
j_--;
}
while(a[i][j_][0] < a[i + 1][_j][0]) _j--;
suff_01[j] = max(suff_01[j], dp[i][j_][0] + pref[i + 1][_j]);
}
}
if(1 < i){
int j_ = 1;
for(int j=1;j<(int)a[i + 1].size();j++){
pref_tp[j] = pref_tp[j - 1];
while(j_ < (int)a[i - 1].size() && a[i - 1][j_][0] <= a[i + 1][j][0]){
pref_tp[j] = max(pref_tp[j], tp[i - 1][j_]);
j_++;
}
}
{
int j_ = (int)a[i - 1].size() - 1, _j = (int)a[i].size() - 1;
for(int j = (int)a[i + 1].size() - 1;j>0;j--){
suff_tp[j] = suff_tp[j + 1];
while(j_ >= 0 && a[i - 1][j_][0] > a[i + 1][j][0]){
while(a[i - 1][j_][0] < a[i][_j][0]) _j--;
suff_tp[j] = max(suff_tp[j], tp[i - 1][j_] + pref[i][_j]);
j_--;
}
while(a[i - 1][j_][0] < a[i][_j][0]) _j--;
suff_tp[j] = max(suff_tp[j], tp[i - 1][j_] + pref[i][_j]);
}
}
}
{
int j_ = 0;
for(int j=1;j<(int)a[i].size();j++){
while(j_ + 1 < (int)a[i + 1].size() && a[i + 1][j_ + 1][0] <= a[i][j][0]){
j_++;
}
mx[i] = max(mx[i], tp[i][j] + pref[i + 1][j_]);
}
}
//~ for(int j=1;j<=n;j++){
//~ mx[i] = max(mx[i], tp[i][j] + pref[i + 1][j]);
//~ if(i > 1){
//~ pref_tp[j] = max(pref_tp[j - 1], tp[i - 1][j]);
//~ }
//~ pref_00[j] = max(pref_00[j - 1], dp[i][j][0] - pref[i][j]);
//~ }
//~ for(int j=n;j>=1;j--){
//~ if(i > 1){
//~ suff_tp[j] = max(suff_tp[j + 1], tp[i - 1][j] + pref[i][j]);
//~ }
//~ suff_11[j] = max(suff_11[j + 1], dp[i][j][1] + pref[i + 1][j]);
//~ suff_01[j] = max(suff_01[j + 1], dp[i][j][0] + pref[i + 1][j]);
//~ }
}
mx[i] = max(mx[i-1], mx[i]);
}
return mx[n];
}
