#include "fish.h"
#include <vector>
#include <array>
#include <iostream>
namespace ruhan {
using namespace std;
int N, M;
int H;
vector<vector<long long>> ss;
vector<vector<array<long long, 2>>> dp;
vector<int> X, Y, W;
bool is_subtask1;
bool is_subtask2;
void init (int N_, int M_, vector<int> X_, vector<int> Y_, vector<int> W_) {
N = N_;
M = M_;
X = X_;
Y = Y_;
W = W_;
H = 0;
for (int i = 0; i < M; i++) {
H = max(H, Y[i]);
}
H++;
is_subtask1 = true;
for (int i = 0; i < M; i++) {
is_subtask1 = is_subtask1 && (X[i] % 2 == 0);
}
is_subtask2 = true;
for (int i = 0; i < M; i++) {
is_subtask2 = is_subtask2 && X[i] <= 1;
}
if (is_subtask1) return;
if (is_subtask2) {
ss = vector<vector<long long>>(2, vector<long long>(H, 0LL));
} else {
ss = vector<vector<long long>>(N, vector<long long>(H, 0LL));
dp = vector<vector<array<long long, 2>>>(N + 1, vector<array<long long, 2>>(H + 1));
}
for (int i = 0; i < M; i++) {
ss[X[i]][Y[i]] += W[i];
}
for (int x = 0; x < (int)ss.size(); x++) {
for (int y = 1; y < H; y++) {
ss[x][y] += ss[x][y-1];
}
}
}
long long get_sum (int x, int ly, int ry) {
ly = max(0, ly);
ry = min(H - 1, ry);
if (x < 0 || x >= N || ry < ly) return 0;
if (ly == 0) return ss[x][ry];
return ss[x][ry] - ss[x][ly-1];
}
long long subtask345 () {
//fill(dp[N].begin(), dp[N].end(), 0LL);
for (int x = N - 1; x >= 0; x--) {
for (int h = 0; h <= H; h++) {
for (int s : {0, 1}) {
const int H1 = s ? h : H;
for (int y = 0; y <= H1; y++) {
long long val = get_sum(x-1,h,y-1) + get_sum(x+1,0,y-1);
val -= get_sum(x, 0, min(h-1,y-1));
val += dp[x+1][y][y < h];
if (x == 4 && h == 0 && s == 1) {
//cerr << "left adding " << get_sum(x-1,h,y-1) << "\n";
//cerr << "right adding " << get_sum(x+1,0,y-1) << "\n";
//cerr << "mid removing " << get_sum(x, 0, min(h-1,y-1)) << "\n";
//cerr << "val(" << y << ") = " << val << "\n";
}
dp[x][h][s] = max(dp[x][h][s], val);
}
if (x < N - 1) {
for (int y = 0; y <= H; y++) {
long long val = get_sum(x, h, y-1);
if (x == 4 && h == 0 && s == 1) {
//cerr << "for y = " << y << ", middle adding " << get_sum(x, h, y-1) << "\n";
}
val += get_sum(x+2, 0, y - 1);
val += x + 2 <= N ? dp[x+2][y][0] : 0;
dp[x][h][s] = max(dp[x][h][s], val);
}
if (x == 4 && h == 0 && s == 1) {
//cerr << "dp -> " << dp[x][h][s] << "\n";
}
}
}
}
}
return dp[0][0][0];
}
long long subtask1 () {
long long res = 0;
for (int i = 0; i < M; i++) {
res += W[i];
}
return res;
}
long long subtask2 () {
long long res = max(get_sum(0, 0, H - 1), get_sum(1, 0, H - 1));
if (N > 2) {
for (int y = 0; y <= H; y++) {
long long val = get_sum(0, 0, y - 1) + get_sum(1, y, H - 1);
res = max(res, val);
}
}
return res;
}
long long calc () {
if (is_subtask1) return subtask1();
if (is_subtask2) return subtask2();
return subtask345();
}
};
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
ruhan::init(N, M, X, Y, W);
return ruhan::calc();
}
