#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, ans;
vector<vector<pair<int, ll> > > f(2e5);
vector<vector<ll> > dp1(2e5);
vector<vector<ll> > dp2(2e5);
ll solve2() {
f[1].push_back({n + 1, 0});
f[2].push_back({n + 1, 0});
sort(f[1].begin(), f[1].end());
sort(f[2].begin(), f[2].end());
ll sum1 = 0, sum2 = 0, h, nxt = 0;
for (auto p: f[1]) sum1 += p.second;
for (auto p: f[2]) sum2 += p.second;
if (n == 2) return max(sum1, sum2);
ans = sum2;
for (auto p: f[2]) {
h = p.first - 1;
while (h >= f[1][nxt].first) sum2 += f[1][nxt++].second;
ans = max(ans, sum2);
sum2 -= p.second;
}
return ans;
}
void get_dp1(int i, int j) {
ll h0, h = f[i][j].first - 1, val = 0;
for (auto p: f[i]) if (p.first <= h) val -= p.second;
for (auto p: f[i + 1]) if (p.first <= h) val += p.second;
for (int k = 0; k < f[i - 1].size(); k++) {
h0 = f[i - 1][k].first - 1;
if (h0 < h) continue;
dp1[i][j] = max(dp1[i][j], dp1[i - 1][k] + val);
dp1[i][j] = max(dp1[i][j], dp2[i - 1][k] + val);
}
ans = max(ans, dp1[i][j]);
}
void get_dp2(int i, int j) {
ll h0, h = f[i][j].first - 1, val = 0, nxt = 0;
for (auto p: f[i - 1]) if (p.first <= h) val += p.second;
for (auto p: f[i + 1]) if (p.first <= h) val += p.second;
for (int k = 0; k < f[i - 1].size(); k++) {
h0 = f[i - 1][k].first - 1;
if (h0 >= h) break;
if (k) val -= f[i - 1][k - 1].second;
while (h0 >= f[i][nxt].first) val -= f[i][nxt++].second;
dp2[i][j] = max(dp2[i][j], dp2[i - 1][k] + val);
}
if (i == 1) {
ans = max(ans, dp2[i][j]);
return;
}
val = nxt = 0;
for (auto p: f[i - 1]) if (p.first <= h) val += p.second;
for (auto p: f[i + 1]) if (p.first <= h) val += p.second;
for (int k = 0; k < f[i - 2].size(); k++) {
h0 = f[i - 2][k].first - 1;
while (h0 >= f[i - 1][nxt].first && h0 >= f[i - 1][nxt].first) val -= f[i - 1][nxt++].second;
dp2[i][j] = max(dp2[i][j], dp1[i - 2][k] + val);
dp2[i][j] = max(dp2[i][j], dp2[i - 2][k] + val);
}
ans = max(ans, dp2[i][j]);
}
ll solve() {
f[0].push_back({1, 0});
for (int i = 0; i <= n + 1; i++) {
f[i].push_back({n + 1, 0});
sort(f[i].begin(), f[i].end());
}
dp1[0] = dp2[0] = {0ll, ll(-1e18)};
for (int i = 1; i <= n; i++) {
dp1[i].resize(f[i].size(), 0);
dp2[i].resize(f[i].size(), 0);
for (int j = 0; j < f[i].size(); j++) {
get_dp1(i, j);
get_dp2(i, j);
}
}
return ans;
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
n = N;
m = M;
ll sum = 0;
for (int i = 0; i < m; i++) {
X[i]++;
Y[i]++;
f[X[i]].push_back({Y[i], W[i]});
sum += W[i];
}
bool st1 = true, st2 = true;
for (int i = 0; i < m; i++) {
if (X[i] % 2 == 0) st1 = false;
if (X[i] > 2) st2 = false;
}
if (st1) return sum;
if (st2) return solve2();
return solve();
}
