#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll max_weights(int N, int M, vector <int> x, vector <int> y, vector <int> w) {
for (auto &it : x)
it++;
vector <ll> sum(N + 2);
vector <map <int, ll>> diff(N + 2);
for (int i = 0; i < M; i++) {
sum[x[i]] += w[i];
diff[x[i] + 1][y[i]] += w[i];
diff[x[i]][y[i]] -= w[i];
}
vector <pair <int, int>> edges;
for (int i = 0; i < 5; i++)
edges.emplace_back(i, (i + 1) % 5);
for (auto it : {0, 1, 4})
edges.emplace_back(it, it);
for (auto it : {2, 3}) {
edges.emplace_back(0, it);
edges.emplace_back(it, 0);
}
vector <ll> dp(5);
dp[3] = dp[4] = -INF;
for (int i = 1; ; i++) {
auto update = [&](ll &ref, ll val) {
if (val > ref)
ref = val;
};
ll curr = 0;
vector <ll> trans(5);
for (auto it : diff[i]) {
curr += it.second;
update(trans[1], curr);
update(trans[4], -curr);
}
trans[2] = sum[i - 1];
trans[3] = sum[i];
for (int j = 0; j < 5; j++)
dp[j] += trans[j];
if (i == N + 1)
break;
vector <ll> nxt(5, -INF);
for (auto it : edges)
update(nxt[it.second], dp[it.first]);
dp = nxt;
}
return max({dp[0], dp[3], dp[4], 0ll});
}
