#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define mp make_pair
using ll = long long;
using ii = pair<int, int>;
int N, M;
vector<int> X, Y, W;
vector<vector<ll> > mem;
vector<ii> col[100005];
ll dp(int p, int ty) {
ll ret = 0;
if (ty == 0) {
if (p == 0) {
return 0;
}
if (p < 0) {
return -(ll)1e16;
}
if (mem[p][ty] != -1) {
return mem[p][ty];
}
ret = max({ret, dp(p - 1, 0), dp(p - 1, 1)});
if (p && !col[p - 1].empty()) {
ret = max(ret, dp(col[p - 1][0].second, 2));
}
} else if (ty == 1) {
if (p == 0) {
return 0;
}
if (p < 0) {
return -(ll)1e16;
}
if (mem[p][ty] != -1) {
return mem[p][ty];
}
ret = max({ret, dp(p - 1, 0), dp(p - 1, 1)});
if (p && !col[p - 1].empty()) {
ret = max(ret, dp(col[p - 1][0].second, 2));
ret = max(ret, dp(col[p - 1].back().second, 3));
}
} else if (ty == 2) {
if (mem[p][ty] != -1) {
return mem[p][ty];
}
int x = X[p], y = Y[p];
ll sum_all = 0;
int ptr = lower_bound(col[x].begin(), col[x].end(), mp(y, p)) - col[x].begin();
assert(ptr != (int)col[x].size());
for (int i = ptr; i < (int)col[x].size(); i++) {
sum_all += W[col[x][i].second];
}
ret = max(ret, dp(x - 1, 1) + sum_all);
if (x && !col[x - 1].empty()) {
ll sum_cur = 0;
for (auto [y_p, idx_p] : col[x - 1]) {
if (y_p <= y) {
continue;
}
while (ptr < (int)col[x].size() && y_p > Y[col[x][ptr].second]) {
sum_cur += W[col[x][ptr].second];
ptr++;
}
ret = max(ret, dp(idx_p, 2) + sum_cur);
}
}
} else {
if (mem[p][ty] != -1) {
return mem[p][ty];
}
int x = X[p], y = Y[p];
ll sum_all = 0;
int ptr = lower_bound(col[x].begin(), col[x].end(), mp(y, p)) - col[x].begin();
assert(ptr != (int)col[x].size());
for (int i = ptr; i >= 0; i--) {
sum_all += W[col[x][i].second];
}
ret = max(ret, dp(x, 0) + sum_all);
if (x && !col[x - 1].empty()) {
ll sum_cur = 0;
for (int _ = (int)col[x - 1].size() - 1; _ >= 0; _--) {
auto [y_p, idx_p] = col[x - 1][_];
if (y_p >= y) {
continue;
}
while (ptr >= 0 && y_p < Y[col[x][ptr].second]) {
sum_cur += W[col[x][ptr].second];
ptr--;
}
//~ cout << "DP " << p << ' ' << ty << " TO " << idx_p << ' ' << 3 << ' ' << sum_cur << ' ' << y_p << ' ' << y << '\n';
ret = max(ret, dp(idx_p, 3) + sum_cur);
}
}
}
//~ cout << "DP " << p << ' ' << ty << ' ' << ret << '\n';
return mem[p][ty] = ret;
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
::N = N;
::M = M;
::X = X;
::Y = Y;
::W = W;
mem = vector<vector<ll> >(N + M, vector<ll>(4, -1));
for (int i = 0; i < M; i++) {
col[X[i]].eb(Y[i], i);
}
for (int i = 0; i < N; i++) {
sort(col[i].begin(), col[i].end());
}
return dp(N, 0);
}
