#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define pld pair<ld, ld>
#define NEK 200000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001
using namespace std;
ll max_weights(int n2, int m2, vec<int> x, vec<int> y, vec<int> w1) {
ll n = n2, m = m2;
vec<vec<pii>> f(n);
For(i, m) {
f[x[i]].push_back({ y[i], i });
}
For(i, n) {
f[i].resize(2, { NEK, m });
sort(all(f[i]));
}
vec<vec<ll>> s(n);
For(i, n) {
s[i].resize(5, NEK);
if (i != 0) {
s[i][0] = f[i - 1][0].ff;
s[i][1] = f[i - 1][1].ff;
}
if (i != (n - 1)) {
s[i][2] = f[i + 1][0].ff;
s[i][3] = f[i + 1][1].ff;
}
s[i][4] = -1;
}
vec<vec<vec<ll>>> dp(n + 1, vec<vec<ll>>(5, vec<ll>(5, 0)));
For(j, 5) {
if (s[n - 2][j] == NEK) continue;
For(k, 5) {
if (s[n - 1][k] == NEK) continue;
int v1 = s[n - 2][j];
int v0 = s[n - 1][k];
int plus = 0;
if (f[n - 1][0].ff > v0 && f[n - 1][0].ff <= v1) {
plus += w1[f[n - 1][0].ss];
}
if (f[n - 1][1].ff > v0 && f[n - 1][1].ff <= v1) {
plus += w1[f[n - 1][1].ss];
}
dp[n][j][k] = plus;
}
}
rffor(i, 2, (n-1)) {
For(j, 5) {
if (s[i - 2][j] == NEK) continue;
For(k, 5) {
if (s[i - 1][k] == NEK) continue;
For(l, 5) {
if (s[i][l] == NEK) continue;
ll v2 = s[i - 2][j];
ll v1 = s[i - 1][k];
ll v0 = s[i][l];
ll plus = 0;
if (f[i - 1][0].ff > v1 && f[i - 1][0].ff <= max(v0, v2)) {
plus += w1[f[i - 1][0].ss];
}
if (f[i - 1][1].ff > v1 && f[i - 1][1].ff <= max(v0, v2)) {
plus += w1[f[i - 1][1].ss];
}
dp[i][j][k] = max(dp[i][j][k], dp[i + 1][k][l] + plus);
}
}
}
}
ll maxi = 0;
For(j, 5) {
if (s[0][j] == NEK) continue;
For(k, 5) {
if (s[1][k] == NEK) continue;
int v0 = s[0][j];
int v1 = s[1][k];
int plus = 0;
if (f[0][0].ff > v0 && f[0][0].ff <= v1) {
plus += w1[f[0][0].ss];
}
if (f[0][1].ff > v0 && f[0][1].ff <= v1) {
plus += w1[f[0][1].ss];
}
maxi = max(maxi, plus + dp[2][j][k]);
}
}
return maxi;
}
/*
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
vec<int> x(m), y(m), w(m);
For(i, m) {
cin >> x[i] >> y[i] >> w[i];
}
cout << max_weights(n, m, x, y, w) << '\n';
return 0;
}*/
