//#include "fish.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 3e2 + 10;
const int M = 4e5 + 10;
ll col_sm[MAX_N][MAX_N];
ll dp[MAX_N][MAX_N][MAX_N];
ll dp_pref[MAX_N][MAX_N][MAX_N];
ll dp_suff[MAX_N][MAX_N][MAX_N];
ll pref_mx[MAX_N][MAX_N][MAX_N];
ll dpp[MAX_N][MAX_N][MAX_N];
ll esim[M][2][2];
ll f(int r, int c) {
if (r == -1) return 0;
return col_sm[r][c];
}
ll sm(int c, int r1, int r2) {
return f(c, r2) - f(c, r1 - 1);
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
if (N <= 300) {
for (int i = 0; i < M; i++) {
col_sm[X[i]][Y[i]] = W[i];
}
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
col_sm[i][j] += col_sm[i][j - 1];
}
}
for (int h1 = 0; h1 <= N; h1++) {
for (int h2 = 0; h2 <= N; h2++) {
if (h1 >= h2) dp[1][h1][h2] = sm(1, h2, h1 - 1);
else dp[1][h1][h2] = sm(0, h1, h2 - 1);
}
}
for (int h1 = 0; h1 <= N; h1++) {
for (int h2 = 0; h2 <= N; h2++) {
pref_mx[1][h1][h2] = max(dp[1][h1][h2], pref_mx[1][h1 - 1][h2]);
if (h1 >= h2) {
dp_pref[1][h1][h2] = max(dp_pref[1][h1 - 1][h2], dp[1][h1][h2] - sm(1, h2, h1 - 1));
}
}
}
for (int h1 = N; h1 >= 0; h1--) {
for (int h2 = 0; h2 <= h1; h2++) {
dp_suff[1][h1][h2] = max(dp[1][h1][h2], dp_suff[1][h1 + 1][h2]);
}
}
for (int i = 2; i < N; i++) {
for (int h1 = 0; h1 <= N; h1++) {
for (int h2 = 0; h2 <= N; h2++) {
if (h1 >= h2) {
dp[i][h1][h2] = pref_mx[i - 1][N][h1] + sm(i, h2, h1 - 1);
}
else {
dp[i][h1][h2] = pref_mx[i - 1][h1][h1] + sm(i - 1, h1, h2 - 1);
dp[i][h1][h2] = max(dp[i][h1][h2], dp_suff[i - 1][h2][h1]);
dp[i][h1][h2] = max(dp[i][h1][h2], dp_pref[i - 1][h2][h1] + sm(i - 1, h1, h2 - 1));
}
}
}
for (int h1 = 0; h1 <= N; h1++) {
for (int h2 = 0; h2 <= N; h2++) {
pref_mx[i][h1][h2] = max(dp[i][h1][h2], pref_mx[i][h1 - 1][h2]);
if (h1 >= h2) {
dp_pref[i][h1][h2] = max(dp_pref[i][h1 - 1][h2], dp[i][h1][h2] - sm(i, h2, h1 - 1));
}
}
}
for (int h1 = N; h1 >= 0; h1--) {
for (int h2 = 0; h2 <= h1; h2++) {
dp_suff[i][h1][h2] = max(dp[i][h1][h2], dp_suff[i][h1 + 1][h2]);
}
}
}
ll mx = 0;
for (int h1 = 0; h1 <= N; h1++) {
for (int h2 = 0; h2 <= N; h2++) {
mx = max(mx, dp[N - 1][h1][h2]);
}
}
return mx;
}
bool ch = true;
ll sm = 0;
for (int i = 0; i < M; i++) {
if (X[i] % 2 == 1) {
ch = false;
}
sm += W[i];
}
if (ch) return sm;
bool ch2 = true;
for (int i = 0; i < M; i++) {
if (X[i] > 1) ch2 = false;
}
if (ch2) {
bool ch0 = false, ch1 = false;
for (int i = 0; i < M; i++) {
if (X[i] == 0) ch0 = true;
else ch1 = true;
}
if (!ch1 || !ch0) return sm;
sm = 0;
map <pair<int, int>, int> mp;
for (int i = 0; i < M; i++) {
mp[{ X[i], Y[i] }] = W[i];
if (X[i] == 1) sm += W[i];
}
ll ans = sm;
for (int i = 0; i < N; i++) {
sm -= mp[{ 1, i }];
sm += mp[{ 0, i }];
ans = max(ans, sm);
}
return ans;
}
map <pair<int, int>, int> mp;
for (int i = 0; i < M; i++) {
mp[{ X[i], Y[i] }] = W[i];
}
esim[1][0][0] = 0;
esim[1][0][1] = mp[{ 0, 0 }];
esim[1][1][0] = mp[{ 1, 0 }];
esim[1][1][1] = 0;
for (int i = 2; i < N; i++) {
esim[i][0][0] = max(esim[i - 1][1][0], esim[i - 1][0][0]);
esim[i][1][1] = max(esim[i - 1][1][1], esim[i - 1][0][1]);
esim[i][0][1] = max(esim[i - 1][1][0], esim[i - 1][0][0] + mp[{ i - 1, 0 }]);
esim[i][1][0] = max(esim[i - 1][0][1], esim[i - 1][1][1]) + mp[{ i, 0 }];
}
return max({ esim[N - 1][0][0], esim[N - 1][0][1],
esim[N - 1][1][0], esim[N - 1][1][1] });
}
/*
int main() {
//3 2
//0 0 1
//1 1 1
//cout << max_weights(3, 2, { 0, 1 }, { 0, 1 }, { 1, 1 });
}
*/
