#include <bits/stdc++.h>
using namespace std;
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)
template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }
const int MAXN = 1e5 + 5;
namespace sub1 {
bool check(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
REP(i, M) if(X[i] % 2 == 1) return false;
return true;
}
long long Main(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
long long ans = 0;
REP(i, M) ans += W[i];
return ans;
}
}
namespace sub2 {
long long pre[2][MAXN];
bool check(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
REP(i, M) if(X[i] > 1) return false;
return true;
}
long long Main(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
long long ans = 0;
REP(i, M) pre[X[i]][Y[i]] += W[i];
FOR(i, 1, N - 1) {
pre[0][i] += pre[0][i - 1];
pre[1][i] += pre[1][i - 1];
}
ans = max(pre[0][N - 1], pre[1][N - 1]);
if(N == 2) return ans;
REP(i, N) {
long long val = pre[1][N - 1] - pre[1][i];
maximize(ans, val + pre[0][i]);
}
return ans;
}
}
namespace sub3 {
const int MAXN = 1e5 + 5;
bool check (int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
REP(i, M) if(Y[i]) return false;
return true;
}
long long dp[MAXN][2][2], a[MAXN];
long long Main(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
long long ans = 0;
REP(i, M) a[X[i] + 1] += W[i];
FOR(i, 1, N) {
dp[i][1][0] = max({dp[i - 1][0][0] + a[i - 1] + a[i + 1], dp[i - 1][0][1] + a[i + 1], dp[i - 1][1][0] - a[i] + a[i + 1]});
dp[i][0][0] = max(dp[i - 1][0][0], dp[i - 1][0][1]);
dp[i][0][1] = dp[i - 1][1][0];
maximize(ans, dp[i][1][0]);
maximize(ans, dp[i][0][0]);
maximize(ans, dp[i][0][1]);
// cout << dp[i][1][0] << " \n"[i == N];
}
return ans;
}
}
long long max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
if(sub1::check(N, M, X, Y, W)) return sub1::Main(N, M, X, Y, W);
if(sub2::check(N, M, X, Y, W)) return sub2::Main(N, M, X, Y, W);
if(sub3::check(N, M, X, Y, W)) return sub3::Main(N, M, X, Y, W);
return 0;
}
