#include "fish.h"
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 1e5 + 5;
int n, m;
ll x[3 * mxn + 1], y[3 * mxn + 1], w[3 * mxn + 1];
vt<ll> take[mxn + 1], notake[mxn + 1], pref[mxn + 1];
ll mxval[mxn + 1];
vt<ll> prefmx[mxn + 1], sufmx[mxn + 1], prefmx2[mxn + 1], sufmx2[mxn + 1];
vt<ll>comp[mxn + 1];
void ckmax(ll &a, ll b){
a = max(a, b);
}
int getr(int id, int x){
return(lower_bound(comp[id].begin(), comp[id].end(), x) - comp[id].begin() + 1);
}
int getl(int id, int x){
return(upper_bound(comp[id].begin(), comp[id].end(), x) - comp[id].begin());
}
ll solve(){
ll ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= sz(comp[i]); j++){
if(i > 1){
notake[i][j] = take[i][j] = pref[i - 1][getl(i - 1, comp[i][j - 1])];
ckmax(take[i][j], sufmx[i - 1][getr(i - 1, comp[i][j - 1])] - pref[i][j]);
ckmax(take[i][j], prefmx[i - 1][getl(i - 1, comp[i][j - 1])]);
ckmax(take[i][j], prefmx2[i - 1][getl(i - 1, comp[i][j - 1])] + pref[i - 1][getl(i - 1, comp[i][j - 1])]);
ckmax(notake[i][j], prefmx[i - 1][sz(comp[i - 1])]);
ckmax(notake[i][j], prefmx2[i - 1][getl(i - 1, comp[i][j - 1])] + pref[i - 1][getl(i - 1, comp[i][j - 1])]);
}
if(i > 2){
ckmax(take[i][j], prefmx[i - 2][getl(i - 2, comp[i][j - 1])] + pref[i - 1][getl(i - 1, comp[i][j - 1])]);
ckmax(take[i][j], sufmx[i - 2][getr(i - 2, comp[i][j - 1])]);
}if(i > 3){
ckmax(take[i][j], mxval[i - 3] + pref[i - 1][getl(i - 1, comp[i][j - 1])]);
ckmax(notake[i][j], mxval[i - 3] + pref[i - 1][getl(i - 1, comp[i][j - 1])]);
}
ll tmp = take[i][j];
if(i < n){
tmp += pref[i + 1][getl(i + 1, comp[i][j - 1])];
}
ckmax(ans, tmp);
if(i < n)ckmax(mxval[i], take[i][j] + pref[i + 1][getl(i + 1, comp[i][j - 1])]);
//cout << i << " " << comp[i][j - 1] << " " << take[i][j] << "\n";
}
for(int j = 1; j <= sz(comp[i]); j++){
prefmx[i][j] = max(prefmx[i][j - 1], take[i][j]);
prefmx2[i][j] = max(prefmx2[i][j - 1], notake[i][j] - pref[i][j]);
}
for(int j = sz(comp[i]); j >= 1; j--){
if(i < n)sufmx[i][j] = max(sufmx[i][j + 1], take[i][j] + pref[i + 1][getl(i + 1, comp[i][j - 1])]);
}
// sp3[i].init();
}
return(ans);
}
map<int, ll>cost[mxn + 1];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W){
n = N; m = M;
ll ans =0;
for(int i = 1; i <= m; i++){
x[i] = ++X[i - 1]; y[i] = ++Y[i - 1]; w[i] = W[i - 1];
cost[x[i]][y[i]] += w[i];
for(int j = max(x[i] - 1, (ll)1); j <= min(x[i] + 1, (ll)n); j++){
comp[j].pb(y[i]);
}
}
for(int i = 1; i <= n; i++){
comp[i].pb(1);
sort(comp[i].begin(), comp[i].end());
comp[i].resize(unique(comp[i].begin(), comp[i].end()) - comp[i].begin());
int need = sz(comp[i]) + 3;
take[i].resize(need); notake[i].resize(need); pref[i].resize(need); prefmx[i].resize(need); prefmx2[i].resize(need); sufmx[i].resize(need);
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= sz(comp[i]); j++){
pref[i][j] = pref[i][j - 1] + cost[i][comp[i][j - 1]];
}
}
return(solve());
}
/*
int main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> X(M), Y(M), W(M);
for (int i = 0; i < M; ++i) {
assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
}
long long result = max_weights(N, M, X, Y, W);
printf("%lld\n", result);
return 0;
}
*/
//741526820812
