#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 4e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , c[N];
deque<pair<int,int>>v[N + 5];
vector<ll>dp[N + 5] , d[N + 5];
ll max_weights(int n, int m , vector<int>a , vector<int>b , vector<int>c){
ll i , j , l , r , s = 0 , f , x , y , k ,ans = 0;
for(i = 0; i < m; i++)
v[a[i]].pb({b[i], c[i]});
for(i = 0; i < n; i++){
sort(all(v[i]));
if(v[i].size() == 0 || v[i].front().fi != 0)
v[i].push_front({0 , 0});
v[i].pb({n , 0});
d[i].resize(v[i].size() , 0);
dp[i].resize(v[i].size() , 0);
if(i == 0)
continue;
l = 0 , s= 0;
for(j = 0; j < v[i].size(); j++){
while(l < v[i - 1].size() && v[i - 1][l].fi < v[i][j].fi)
s += v[i - 1][l].se , l++;
f = 0;
for(x = 0; x < l; x++)
dp[i][j] = max(dp[i][j] , dp[i - 1][x] + s - f) , f += v[i - 1][x].se;
if(v[i][l].fi == v[i][j].fi)
dp[i][j] = max(dp[i][j] , max(dp[i - 1][l] , d[i - 1][l]));
r = l;
f = 0;
if(i > 1)
for(x = 0; x < v[i - 2].size(); x++){
while(r < v[i - 1].size() && v[i - 1][r].fi < v[i - 2][x].fi)
f += v[i - 1][r].se , r++;
dp[i][j] = max(dp[i][j] , s + f + max(dp[i - 2][x] , d[i - 2][x]));
}
f = 0 , r = j;
for(x = 0; x < v[i - 1].size(); x++){
while(r < v[i].size() && v[i][r].fi < v[i - 1][x].fi)
f += v[i][r].se , r++;
d[i][j] = max(d[i][j] , max(dp[i - 1][x] , d[i - 1][x]) + f);
dp[i][j] = max(dp[i][j] , max(dp[i - 1][x] , d[i - 1][x]));
}
d[i][j] = max(d[i][j] , dp[i][j]);
ans = max({ans , dp[i][j] , d[i][j]});
}
}
return ans;
}
/*
int main(){
TL;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cout<<max_weights(4, 4, {3, 0 , 2 , 1}, {0, 0, 1 , 3}, {1 , 4 , 1 , 2});
}*/
// Author : حسن
