#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 1e5 + 5, MAX_M = 3e5 + 5;
const lint INF = 5e18;
int n, m;
int x[MAX_M], y[MAX_M];
lint w[MAX_M];
lint val[MAX_N];
void precomp() {
for (int i = 0; i < m; i++)
val[x[i]] = w[i];
}
lint dp[MAX_N];
bool seen[MAX_N];
lint find_dp(int i) {
assert(i >= -1);
if (i == -1) return 0;
if (i == 0) return val[0];
if (seen[i]) return dp[i];
lint leave = find_dp(i - 1);
lint leave_prev = val[i] + find_dp(i - 2);
lint take_prev = (i == 1 || i == n - 1) ? -INF : val[i] + val[i - 1] + find_dp(i - 3);
dp[i] = max({leave, leave_prev, take_prev});
seen[i] = true;
return dp[i];
}
void init() {
for (int i = 0; i < n; i++) {
seen[i] = false;
dp[i] = -INF;
val[i] = 0;
}
}
lint max_weights(int tmp_n, int tmp_m, vector<int> tmp_x, vector<int> tmp_y, vector<int> tmp_w) {
n = tmp_n;
m = tmp_m;
init();
for (int i = 0; i < m; i++) {
x[i] = tmp_x[i];
y[i] = tmp_y[i];
w[i] = tmp_w[i];
}
precomp();
lint ans = find_dp(n - 1);
return ans;
}
