#include <bits/stdc++.h>
     
using namespace std;
     
#define ll long long 
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;

const int N=100007;

set<int>S[N];
vector<int>points[N];

vector<ll>DP[2][N];
vector<ll>L[N];
vector<ll>R[N];
vector<ll>M[N];


vector<pair<int,int>>V[N];
     
ll max_weights(int n,int m,vector<int>X,vector<int>Y,vector<int>W)
{
	for(int i=0;i<m;i++)
	{
		X[i]++;
		Y[i]++;
		S[X[i]].insert(Y[i]-1);
		S[X[i]-1].insert(Y[i]);
		S[X[i]+1].insert(Y[i]);
		V[X[i]].pb({Y[i],W[i]});
	}
	for(int i=1;i<=n;i++)
	{
		S[i].insert(0);
		sort(all(V[i]));
		for(auto x:S[i]) points[i].pb(x);
		DP[0][i].resize(sz(points[i]),0);
		DP[1][i].resize(sz(points[i]),0);
		L[i].resize(sz(points[i]),0);
		R[i].resize(sz(points[i]),0);
		M[i].resize(sz(points[i]),0);
	}
	for(int i=1;i<=n;i++)
	{
		vector<pair<pair<int,ll>,int>>P;
		for(auto [y,c]:V[i-1]) P.pb({{y,-c},1});
		for(auto [y,c]:V[i]) P.pb({{y,-c},2});
		for(auto [y,c]:V[i+1]) P.pb({{y,-c},3});
		for(int j=0;j<sz(points[i]);j++) P.pb({{points[i][j],j},0});
		sort(all(P));
		ll sum1=0,sum2=0,sum3=0;
		if(auto [y,c]:P)
		{
			if(c==0) 
			{
				L[i][y.nd]=sum1;
				M[i][y.nd]=sum2;
				R[i][y.nd]=sum3;
			}
			else if(c==1) sum1+=-y.nd;
			else if(c==2) sum2+=-y.nd;
			else sum3+=-y.nd;
		}
		
		
		
		
	/*	ll sum=0;
		for(auto [y,c]:P)
		{
			if(c>=0) L[i][c]=sum;
			else sum+=-c;
		}
		P.clear();
		for(auto [y,c]:V[i+1]) P.pb({y,-c});
		for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j});
		sort(all(P));
		sum=0;
		for(auto [y,c]:P)
		{
			if(c>=0) R[i][c]=sum;
			else sum+=-c;
		}
		P.clear();
		for(auto [y,c]:V[i]) P.pb({y,-c});
		for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j});
		sort(all(P));
		sum=0;
		for(auto [y,c]:P)
		{
			if(c>=0) M[i][c]=sum;
			else sum+=-c;
		}*/
	}
	for(int i=0;i<sz(points[1]);i++) DP[1][1][i]=-infl;
	ll ans=0;
	for(int i=2;i<=n;i++)
	{
		vector<pair<int,int>>P;
		for(int j=0;j<sz(points[i-2]);j++) P.pb({points[i-2][j],-j-1});
		//for(auto y:points[i-2]) P.pb({y,0});
		for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j});
		//for(auto y:points[i]) P.pb({y,1});
		sort(all(P));
		ll mx=0;
		for(auto [y,c]:P)
		{
			if(c<0) mx=max({mx,DP[0][i-2][-c-1],DP[1][i-2][-c-1]});
			else DP[0][i][c]=max(DP[0][i][c],mx+L[i][c]);
		}
		reverse(all(P));
		mx=0;
		for(auto [y,c]:P)
		{
			if(c<0) mx=max(mx,max(DP[0][i-2][-c-1],DP[1][i-2][-c-1])+R[i-2][-c-1]);
			else DP[0][i][c]=max(DP[0][i][c],mx);
		}
		P.clear();
		for(int j=0;j<sz(points[i-1]);j++) P.pb({points[i-1][j],-j-1});
		for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j});
		sort(all(P));
		mx=0;
		for(auto [y,c]:P)
		{
			if(c<0) mx=max(mx,DP[0][i-1][-c-1]-M[i-1][-c-1]);
			else DP[0][i][c]=max(DP[0][i][c],mx+L[i][c]);
		}
		reverse(all(P));
		mx=0;
		for(auto [y,c]:P)
		{
			if(c<0) mx=max(mx,max(DP[0][i-1][-c-1],DP[1][i-1][-c-1])+R[i-1][-c-1]);
			else DP[1][i][c]=max(DP[1][i][c],mx-M[i][c]);
		}
		for(int j=0;j<sz(points[i]);j++) ans=max({ans,DP[0][i][j],DP[1][i][j]});
	}
	
	return ans;
}
 /*
int main()
{
	int n=100000,m=100000;
	//cin>>n>>m;
	vector<int>X(m),Y(m),C(m);
	for(int i=0;i<m;i++)
	{
		//cin>>X[i]>>Y[i]>>C[i];
		X[i]=rand()%n;
		Y[i]=rand()%n;
		C[i]=rand()%1000000+1;
	}
	cout<<max_weights(n,m,X,Y,C)<<endl;
	return 0;
}*/
    

answer.code: In function ‘long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)’:
answer.code:53:26: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
   53 |                 for(auto [y,c]:V[i-1]) P.pb({{y,-c},1});
      |                          ^
answer.code:54:26: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
   54 |                 for(auto [y,c]:V[i]) P.pb({{y,-c},2});
      |                          ^
answer.code:55:26: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
   55 |                 for(auto [y,c]:V[i+1]) P.pb({{y,-c},3});
      |                          ^
answer.code:59:25: error: expected unqualified-id before ‘[’ token
   59 |                 if(auto [y,c]:P)
      |                         ^
answer.code:61:28: error: ‘c’ was not declared in this scope
   61 |                         if(c==0)
      |                            ^
answer.code:63:38: error: ‘y’ was not declared in this scope
   63 |                                 L[i][y.nd]=sum1;
      |                                      ^
answer.code:67:46: error: ‘y’ was not declared in this scope
   67 |                         else if(c==1) sum1+=-y.nd;
      |                                              ^
answer.code:68:46: error: ‘y’ was not declared in this scope
   68 |                         else if(c==2) sum2+=-y.nd;
      |                                              ^
answer.code:69:37: error: ‘y’ was not declared in this scope
   69 |                         else sum3+=-y.nd;
      |                                     ^
answer.code:113:26: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
  113 |                 for(auto [y,c]:P)
      |                          ^
answer.code:120:26: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
  120 |                 for(auto [y,c]:P)
      |                          ^
answer.code:130:26: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
  130 |                 for(auto [y,c]:P)
      |                          ^
answer.code:137:26: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
  137 |                 for(auto [y,c]:P)
      |                          ^