#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
//long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
//long long pref[2][N+1];
//memset(pref,0,sizeof(pref));
//for (int i = 0; i < M; i++) {
//pref[X[i]][Y[i]+1]+=W[i];
//}
//for (int i = 1; i <= N; i++) {
//pref[0][i]+=pref[0][i-1];
//pref[1][i]+=pref[1][i-1];
//}
//if (N<3) return max(pref[0][N], pref[1][N]);
//long long ans=max(pref[0][N], pref[1][N]);
//for (int i = 1; i <= N; i++) {
//ans=max(ans,pref[0][i]+pref[1][n]-pref[1][i-1]);
//}
//return ans;
//}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
int w[N+5];memset(w,0,sizeof(w));
for (int i = 0; i < M; i++) {
w[X[i]] = W[i];
}
int dp[N][2][2];
dp[1][0][0]=0;
dp[1][0][1]=w[0]+w[2];
dp[1][1][0]=w[1];
dp[1][1][1]=w[2]; //what a skem
for (int i = 2; i < N; i++) {
dp[i][0][0]=max(dp[i-1][1][0], dp[i-1][0][0]);
dp[i][0][1]=max(dp[i-1][1][0]+w[i+1], dp[i-1][0][0]+w[i+1]+w[i-1]);
dp[i][1][0]=max(dp[i-1][0][1], dp[i-1][1][1]);
dp[i][1][1]=max(dp[i-1][0][1], dp[i-1][1][1])-w[i]+w[i+1];
}
return max(max(dp[N-1][0][0], dp[N-1][0][1]), max(dp[N-1][1][0], dp[N-1][1][1]));
}
//long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
//long long ans = 0; for (int i =0; i < M; i++) ans += W[i];
//return ans;
//}
//long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
//long long pref[2][N+1];
//memset(pref,0,sizeof(pref));
//for (int i = 0; i < M; i++) {
//pref[X[i]][Y[i]+1]+=W[i];
//}
//for (int i = 1; i <= N; i++) {
//pref[0][i]+=pref[0][i-1];
//pref[1][i]+=pref[1][i-1];
//}
//long long ans=0;
//for (int i = 1; i <= N; i++) {
//ans=max(ans,pref[0][i]+pref[1][i]-pref[1][i-1]);
//ans=max(ans,pref[1][i]+pref[0][i]-pref[0][i-1]);
//}
//return ans;
//}
//long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
//std::vector<int> W) {
//int weights[N][N+1]; memset(weights,0,sizeof(weights));
//for (int i = 0; i < M; i++) {
//weights[X[i]][Y[i]+1]=W[i];
//}
//int pref[N][N+1];
//for (int i = 0; i < N; i++) {
//pref[i][0]=0;
//for (int j = 1; j <= N; j++) pref[i][j]=pref[i][j-1]+weights[i][j];
//}
//int dp[N][N+1];
////the thing is, we first do dp on N=1. this is to be more convenient i guess?
//for (int i = 0; i <= N; i++) {
////if this is higher than the previous, then of course optimal to take everything above,
//dp[0][i][0]=pref[1][i];
//}
//int store1[N][N+1], store2[N][N+1], store3[N][N+1], store4[N][N+1];
//for (int i = 1; i < N; i++) {
//for (int j = 0; j <= N; j++) {
////left height
////impact: j<=x -> dp[i+1][x][0]=max(dp[i+1][x][0], dp[i][j][0]
////case 1: j > k, j > l
//dp[i][j] = store1[i-1][j]+pref[i+1][j]+pref[i-1][j];
////case 2: j < k, j < l
//dp[i][j]=max(dp[i][j],store2[i-1][j]+pref[i+1][j]);
////case 3: j < k, j > l
//dp[i][j]=max(dp[i][j],store3[i-1][j]+pref[i-1][j]-pref[i][j]+pref[i+1][j]);
////case 4: j < k, j < l
//dp[i][j]=max(dp[i][j],store4[i-1][j]-pref[i][j]+pref[i+1][j]);
////why ?????????????? IM SO SAD RNNNN
//}
////now we update the stores
//store1[i][j] = max(dp[i-1][k][l]-pref[i-1][k]) //where j > k, j > l
//}
//}
//???
