#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll infm = -1e18;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
int n = N, m = M;
bool ind = 1;
int T = 0;
for (int i = 0; i < m; i++){
if (X[i] % 2){
ind = 0;
}
X[i]++; Y[i]++;
T = max(T, X[i]);
}
if (ind){
ll out = 0;
for (int i: W){
out += i;
}
return out;
}
vector<int> d[n + 1];
for (int i = 0; i < m; i++){
d[X[i]].pb(i);
}
T = min(T + 1, n);
vector<vector<ll>> F(T + 1, vector<ll>(n + 1));
for (int i = 1; i <= T; i++){
for (int j: d[i]){
F[i][Y[j]] = W[j];
}
for (int j = 1; j <= n; j++){
F[i][j] += F[i][j - 1];
}
}
vector<vector<vector<ll>>> dp(T + 1, vector<vector<ll>>(n + 1, vector<ll>(2)));
for (int i = 2; i <= T; i++){
vector<ll> pr1(n + 1), pr2(n + 1), pr3(n + 2);
pr1[0] = pr2[0] = infm;
for (int j = 0; j <= n; j++){
if (j != 0){
pr1[j] = pr1[j - 1];
pr2[j] = pr2[j - 1];
}
pr1[j] = max(pr1[j], dp[i - 1][j][0] - F[i - 1][j]);
if (i > 2){
pr2[j] = max(pr2[j], max(dp[i - 2][j][0], dp[i - 2][j][1]));
}
}
if (i > 2){
for (int j = n; j >= 0; j--){
pr3[j] = max(pr3[j + 1], max(dp[i - 2][j][0], dp[i - 2][j][1]) + F[i - 1][j]);
}
}
vector<ll> pr4(n + 2);
for (int j = n; j >= 0; j--){
pr4[j] = max(pr4[j + 1], max(dp[i - 1][j][0], dp[i - 1][j][1]) + F[i][j]);
}
for (int j = 0; j <= n; j++){
dp[i][j][0] = pr1[j] + F[i - 1][j];
if (i > 2){
dp[i][j][0] = max(dp[i][j][0], pr2[j] + F[i - 1][j]);
dp[i][j][0] = max(dp[i][j][0], pr3[j + 1]);
}
dp[i][j][1] = max(0LL, pr4[j + 1] - F[i][j]);
}
}
ll out = 0;
for (int i = 1; i <= T; i++){
for (int j = 0; j <= n; j++){
out = max({out, dp[i][j][0], dp[i][j][1]});
}
}
return out;
}
