#include "fish.h"
#include<bits/stdc++.h>
#define ii pair<int,long long>
#define F first
#define S second
#define iii pair<ii,int>
using namespace std;
long long dp[3000005][3];
vector<iii>pre[100005];
int n;
long long sum(int i,int j){
if(i >= n){
return 0;
}
int posi = lower_bound(pre[i].begin(),pre[i].end(),iii(ii(j+1,0),0)) - pre[i].begin();
posi--;
return pre[i][posi].F.S;
}
long long solve(int i,int j,int k){
int pos = -1;
long long sumi = 0;
if(i >= n){
return 0;
}
if(j < 0 || j > n){
return 0;
}
if(k == 0 || k == 2){
int posi = lower_bound(pre[i].begin(),pre[i].end(),iii(ii(j,0),0)) - pre[i].begin();
j = pre[i][posi].F.F;
pos = pre[i][posi].S;
}
else{
int posi = lower_bound(pre[i].begin(),pre[i].end(),iii(ii(j+1,0),0)) - pre[i].begin();
posi--;
j = pre[i][posi].F.F;
pos = pre[i][posi].S;
}
if(dp[pos][k] != -1){
return dp[pos][k];
}
sumi = sum(i,j);
long long ans = 0;
if(k == 0 || k == 2){
ans = max(ans,solve(i,j+1,k));
long long val = 0;
if(k == 0){
val = sum(i-1,j);
}
long long sum2 = sum(i+1,j);
ans = max(ans,solve(i+1,j,0) - sumi + val);
ans = max(ans,solve(i+1,j,1) + val + sum2);
ans = max(ans,solve(i+2,0,2) + val + sum2);
ans = max(ans,solve(i+2,0,0) + val);
}
else{
long long sum2 = sum(i+1,j);
ans = max(ans,solve(i,j-1,1));
ans = max(ans,solve(i+2,0,0) - sumi);
ans = max(ans,solve(i+2,0,2) - sumi + sum2);
ans = max(ans,solve(i+1,j,1) - sumi + sum2);
}
return dp[pos][k] = ans;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
n = N;
memset(dp,-1,sizeof dp);
long long sum = 0;
for(int i = 0;i < M;i++){
Y[i]++;
pre[X[i]].push_back(iii(ii(Y[i],W[i]),0));
pre[X[i]].push_back(iii(ii(Y[i] - 1,0),0));
if(X[i] > 0){
pre[X[i] - 1].push_back(iii(ii(Y[i],0),0));
}
if(X[i] < n-1){
pre[X[i] + 1].push_back(iii(ii(Y[i],0),0));
}
}
int cur = 0;
for(int i = 0;i < N;i++){
pre[i].push_back(iii(ii(0,0),0));
pre[i].push_back(iii(ii(n,0),0));
sort(pre[i].begin(),pre[i].end());
int m = pre[i].size();
pre[i][0].S = cur;
cur++;
for(int j = 1;j < m;j++){
pre[i][j].F.S += pre[i][j-1].F.S;
pre[i][j].S = cur;
cur++;
}
}
return solve(0,0,2);
}
/*
int main() {
srand(time(0));
int N = 2, M = 1;
//assert(2 == scanf("%d %d", &N, &M));
std::vector<int> X(M), Y(M), W(M);
for (int i = 0; i < M; ++i) {
W[i] = 1000000000;
X[i] = 0;
Y[i] = 0;
//assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
}
long long result = max_weights(N, M, X, Y, W);
printf("%lld\n", result);
return 0;
}
*/
