#include <bits/stdc++.h>
using namespace std;
#include "fish.h"
int const Mx = 1e5 + 10;
int n , m , j , Req , ReqNext;
map<int , int>cost[Mx] , vis[Mx];
vector<int>possible[Mx];
vector<long long>pref[Mx] , dp[2][Mx];
long long max_weights(int N, int M , vector<int> X, vector<int> Y, vector<int> W) {
m = M , n = N;
long long ans = 0;
for(int i = 0 ; i < m ; ++i) {
++X[i];
++Y[i];
possible[X[i] - 1].push_back(Y[i]);
possible[X[i] + 1].push_back(Y[i]);
possible[X[i]].push_back(Y[i]);
cost[X[i]][Y[i]] = W[i];
}
for(int i = 1 ; i <= n + 1 ; ++i) {
possible[i].push_back(0);
vector<int>Cur;
sort(possible[i].begin() , possible[i].end());
for(auto j : possible[i]) if(Cur.size() == 0 || Cur.back() != j) Cur.push_back(j);
possible[i] = Cur;
for(auto j : possible[i]) {
long long cur = 0;
if(pref[i].size()) cur = pref[i].back();
cur += cost[i][j];
pref[i].push_back(cur);
dp[0][i].push_back(0);
dp[1][i].push_back(0);
}
}
long long MaxPref = 0 , MaxSuf = pref[2].back() , MaxDp = 0 , MaxAddDp = 0;
for(int i = 2 ; i <= n ; ++i) {
Req = 0 , ReqNext = 0;
for(int J = 0 ; J < possible[i].size() ; ++J) {
j = possible[i][J];
while(Req + 1 < possible[i - 1].size() && possible[i - 1][Req + 1] <= j) ++Req;
dp[0][i][J] = max(dp[0][i][J] , MaxPref + pref[i - 1][Req]);
dp[1][i][J] = max(dp[1][i][J] , MaxSuf - pref[i][J]);
if(i >= 3) {
dp[0][i][J] = max(dp[0][i][J] , MaxDp + pref[i - 1][Req]);
dp[0][i][J] = max(dp[0][i][J] , MaxAddDp - pref[i - 1][Req]);
}
ans = max(ans , dp[0][i][J]);
ans = max(ans , dp[1][i][J]);
}
MaxPref = MaxSuf = MaxDp = MaxAddDp = 0;
for(int J = 0 ; J < possible[i].size() ; ++J) {
j = possible[i][J];
while(ReqNext + 1 < possible[i + 1].size() && possible[i + 1][ReqNext + 1] <= j) ++ReqNext;
MaxPref = max(MaxPref , dp[0][i][J] - pref[i][J]);
MaxSuf = max(MaxSuf , max(dp[0][i][J] , dp[1][i][J]) + pref[i + 1][ReqNext]);
}
Req = 0;
for(int J = 0 ; J < possible[i - 1].size() ; ++J) {
j = possible[i - 1][J];
while(Req + 1 < possible[i].size() && possible[i][Req + 1] <= j) ++Req;
MaxDp = max(MaxDp , max(dp[0][i - 1][J] , dp[1][i - 1][J]));
MaxAddDp = max(MaxAddDp , max(dp[0][i - 1][J] , dp[1][i - 1][J]) + pref[i][Req]);
}
}
return ans;
}
/*
pref = max Dp - prefi
suf = max Dp - prefi + 1
Pref = max Dp
Suf = max Dp + prefi + 1
*/
