#include <bits/stdc++.h>
#include "fish.h"
// #include "grader.cpp"
using namespace std;
typedef long long ll;
vector<pair<int, int>> vec[(int)2e5 + 10];
int sm(int i, int p){
int res = 0;
for (auto [pos, val] : vec[i])
if (pos <= p)
res += val;
return res;
}
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
vector<int> poss[n + 5];
for (int i = 0; i < m; i ++)
vec[x[i] + 1].push_back({y[i] + 1, w[i]});
ll dp[n + 1][5][2] = {};
for (int i = 0; i < 5; i ++)
poss[0].push_back(0);
for (int i = 1; i <= n; i ++){
poss[i].push_back(0);
for (auto P : vec[i - 1])
poss[i].push_back(P.first);
for (auto P : vec[i + 1])
poss[i].push_back(P.first);
while (poss[i].size() < 5) poss[i].push_back(0);
sort(poss[i].begin(), poss[i].end());
}
for (int k = 0; k < 5; k ++)
for (auto [p, v] : vec[2])
if (p <= poss[1][k])
dp[1][k][0]++, dp[1][k][1]++;
for (int i = 2; i <= n; i ++){
for (int ik = 0; ik < 5; ik ++){
int k = poss[i][ik];
for (int ipk = 0; ipk < 5; ipk ++){
int pk = poss[i - 1][ipk];
if (k >= pk) dp[i][ik][0] = max(dp[i][ik][0], dp[i - 1][ipk][0] - sm(i, pk) + sm(i - 1, k) - sm(i - 1, pk) + sm(i + 1, k));
else dp[i][ik][1] = max(dp[i][ik][1], max(dp[i - 1][ipk][0], dp[i - 1][ipk][1]) - sm(i, k) + sm(i + 1, k));
}
for (int ipk = 0; ipk < 5; ipk ++){
int pk = poss[i - 2][ipk];
dp[i][ik][0] = max(dp[i][ik][0], max(dp[i - 2][ipk][0], dp[i - 2][ipk][1]) - sm(i - 1, pk) + sm(i - 1, max(pk, k)) + sm(i + 1, k));
}
// cout << i << " " << k << " : " << dp[i][ik][0] << ", " << dp[i][ik][1] << endl;
}
}
ll ans = 0;
for (int k = 0; k < 5; k ++)
ans = max(ans, max(dp[n][k][0], dp[n][k][1]));
return ans;
}
