#include <cstdio>
#ifdef DEBUG
#define D(X) X
#else
#define D(X)
#endif
#include <bits/stdc++.h>
#define F first
#define S second
#define ll long long
#define pi 3.14159265359
#define pub push_back
#define pob pop_back
#define pari pair<int,int>
#define parli pair<long, long>
using namespace std;
const int INF = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
vector<vector<ll>> cnt2(3, vector<ll>(n+1, 0));
int odd = 0, mx = 0;
ll all = 0;
for(int i=0; i<m; i++) {
if(x[i]%2==1) {
odd = 1;
}
if(x[i]<=1)
cnt2[x[i]][y[i]+1] += w[i];
all += w[i];
mx = max(mx, x[i]);
}
if(!odd) {
return all;
}
for(int i=0; i<2; i++) {
for(int j=1; j<=n; j++) {
cnt2[i][j] += cnt2[i][j-1];
}
}
if(mx<=1) {
if(n==2) {
return max(cnt2[0][n], cnt2[1][n]);
} else
{
ll res = cnt2[1][n], best = res;
for(int j=1; j<=n; j++) {
res = max(res, res+cnt2[0][j]-cnt2[1][j]);
}
return res;
}
}
vector<vector<ll>> cnt(n + 1, vector<ll>(n+1, 0));
for(int i=0; i<m; i++) {
cnt[x[i]][y[i]+1] += w[i];
}
for(int i=0; i<n; i++) {
for(int j=1; j<=n; j++) {
cnt[i][j] += cnt[i][j-1];
}
}
vector<vector<ll>> pref(n+1, vector<ll>(n+1, 0));
vector<vector<ll>> suf(n+1, vector<ll>(n+1, 0));
vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(n+1, vector<ll>(2, 0)));
ll res = 0;
for(int i=1; i<n; i++) {
if(i==1) {
pref[i-1][0] = 0;
} else
{
pref[i-1][0] = dp[i-2][0][0];
}
for(int j=1; j<=n; j++) {
pref[i-1][j] = max(pref[i-1][j-1], dp[i-1][j][1] - cnt[i-1][j]);
}
suf[i-1][n] = cnt[i][n] + max(dp[i-1][n][0], dp[i-1][n][1]);
for(int j=n-1; j>=1; j--) {
suf[i-1][j] = max(suf[i-1][j+1], max(dp[i-1][j][0], dp[i-1][j][1]) + cnt[i][j]);
}
dp[i][0][0] = dp[i][0][1] = max(suf[i-1][1], dp[i-1][0][0]);
for(int j=1; j<=n; j++) {
dp[i][j][0] = suf[i-1][j] - cnt[i][j];
dp[i][j][1] = cnt[i-1][j] + pref[i-1][j];
if(i>1) {
dp[i][j][1] = max(dp[i][j][1], cnt[i-1][j]+pref[i-2][j]);
dp[i][j][1] = max(dp[i][j][1], suf[i-2][j]);
}
//res = max(res, max(dp[i][j][0], dp[i][j][1]));
}
}
for(int i=0; i<n; i++)
for(int j=0; j<=n; j++) {
for(int bin=0; bin<2; bin++)
res = max(res, dp[i][j][bin]);
}
return res;
}
/*
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
D(freopen("input.txt","r",stdin);)
//D(freopen("ouput.txt","w",stdout);)
int t = 1;
//cin >> t;
loop:
while(t--)
{
int n, m;
cin >> n >> m;
vector<int> x(m), y(m), w(m);
for(int i=0; i<m; i++) {
cin >> x[i];
}
for(int i=0; i<m; i++) {
cin >> y[i];
}
for(int i=0; i<m; i++) {
cin >> w[i];
}
ll res = max_weights(n, m, x, y, w);
cout << res;
}
return 0;
}
*/
