#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) {
//long long w[N+5];memset(w,0,sizeof(w));
//for (int i = 0; i < M; i++) {
//w[X[i]] = W[i];
//}
//long long 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
//}
//}
//???
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
long long weights[N][N+1]; memset(weights,0,sizeof(weights));
for (int i = 0; i < M; i++) {
weights[X[i]][Y[i]+1]=W[i];
}
long long 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 maxh=min(N+1,10);
long long dp[N][maxh][maxh][maxh]; //dp[i][first prev][secondprev][thirdprev];
for (int i = 0; i < maxh; i++) for (int j = 0; j < maxh; j++) for (int k = 0; k < maxh; k++) dp[0][i][j][k]=-2e17;
for (int i = 0; i < maxh; i++) {
dp[0][i][0][0]=pref[1][i];
}
long long store[N][maxh][maxh]; memset(store,0,sizeof(store));
for (int i = 0; i < maxh; i++) for (int j = 0; j < maxh; j++) for (int k = 0; k < maxh; k++) {
store[0][i][j]=max(store[0][i][j], dp[0][i][j][k]);
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < maxh; j++) {
for (int k = 0; k < maxh; k++) {
for (int l = 0; l < maxh; l++) {
dp[i][j][k][l]=store[i-1][k][l]+pref[i-1][max(j,l)]-pref[i-1][k]+max(0ll, pref[i][k]-pref[i][j])+pref[i+1][j];
}
}
}
for (int x = 0; x < maxh; x++) for (int j = 0; j < maxh; j++) for (int k = 0; k < maxh; k++) {
store[i][x][j]=max(store[i][x][j], dp[i][x][j][k]);
}
}
long long ans = 0;
for (int i = 0; i < maxh; i++) for (int j =0; j < maxh; j++) for (int k = 0; k < maxh; k++) ans=max(ans, dp[N-1][i][j][k]);
return ans;
}
