#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <cassert>
#include <iomanip>
#include <cmath>
#include <bitset>
using namespace std;
using int64 = long long;
int64 max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<int64> sum_cols(N + 2);
vector<vector<pair<int, int>>> vec_cols(N + 2);
for (int i = 0; i < M; i++)
X[i]++;
for (int i = 0; i < M; i++) {
sum_cols[X[i]] += W[i];
vec_cols[X[i]].emplace_back(Y[i], W[i]);
}
for (int i = 0; i <= N + 1; i++) {
sort(vec_cols[i].begin(), vec_cols[i].end());
}
vector<int64> dp(N + 2, 0);
for (int i = 2; i <= N + 1; i++) {
dp[i] = dp[i-1];
// i - 2 ... i, take [i-2], [i]
dp[i] = max(dp[i], (i - 3 >= 0 ? dp[i - 3] : 0) + sum_cols[i-2] + sum_cols[i]);
// i - 4 ... i, take [i-4], [i-2], [i]
if (i - 4 >= 0) {
dp[i] = max(dp[i],
(i - 5 >= 0 ? dp[i - 5] : 0) + sum_cols[i-4] + sum_cols[i-2] + sum_cols[i]);
}
// i - 3 .. i
if (i - 3 >= 0) {
int64 prev = (i - 4 >= 0 ? dp[i - 4] : 0);
// Take all of [i], [i-3]
dp[i] = max(dp[i], prev + sum_cols[i] + sum_cols[i-3]);
auto build_stair = [&] (int a, int b, int f) {
int64 tmp = prev + sum_cols[f];
// adj on a
// building over b
int at = -1;
int64 gained = 0;
int64 lost = sum_cols[b];
int64 res = tmp + gained + lost;
int idx = 0;
for (auto el : vec_cols[a]) {
gained += el.second;
// lost
while (idx < vec_cols[b].size() && vec_cols[b][idx].first <= el.first) {
lost -= vec_cols[b][idx].second;
idx++;
}
res = max(res, tmp + gained + lost);
}
return res;
};
dp[i] = max(dp[i], build_stair(i - 3, i - 2, i));
dp[i] = max(dp[i], build_stair(i, i - 1, i - 3));
}
}
return dp[N + 1];
}
// int main() {
// // cerr << max_weights(
// // 5,
// // 4,
// // vector<int>{0, 1, 4, 3},
// // vector<int>{2, 1, 4, 3},
// // vector<int>{5, 2, 1, 3}
// // ) << "\n";
// // cerr << max_weights(
// // 4,
// // 4,
// // vector<int>{3, 0, 1, 2},
// // vector<int>{3, 0, 2, 2},
// // vector<int>{100, 50, 1000, 10}
// // ) << "\n";
// return 0;
// }
