#include <bits/stdc++.h>
using namespace std;
#define maxn 300010
int X[maxn], Y[maxn], weight[maxn];
int n, maxcord;
vector <int> checkpoints[maxn];
vector < pair <int, int > > store[maxn];
vector <long long int> dp_1[maxn], dp_2[maxn], dp_3[maxn], dp_4[maxn];
/*
dp[i][1] --> i is in increasing range, right contribution not counted
dp[i][2] --> i is in decreasing range, right contribution not counted
dp[i][3] --> segment of i had ended, right contribution counted
*/
long long int st[8*maxn+10], lz[8*maxn+10];
int marked[8*maxn+10];
void push (int N, int L, int R){
if (marked[N]){
st[N]+=lz[N];
int mid= (L+R)/2;
if (L <= mid) {
marked[2*N+1]=1;
lz[2*N+1]+=lz[N];
}
if (mid+1<=R){
marked[2*N+2]=1;
lz[2*N+2]+=lz[N];
}
lz[N]=0;
marked[N]=0;
}
}
void upd (int N, int L, int R, int S, int E, long long int val){
if (L>R) return;
push (N, L, R);
if (L>=S and R<=E){
lz[N]=val;
marked[N]=1;
push(N, L, R);
return;
}
if (L>E or S>R) return;
int mid= (L+R)/2;
upd (2*N+1, L, mid, S, E, val);
upd (2*N+2, mid+1, R, S, E, val);
st[N]= max(st[2*N+1], st[2*N+2]);
}
long long int query (int N, int L, int R, int S, int E){
if (L>R) return -1;
push(N, L, R);
if (L>E or S>R) return -1;
if (L>=S and R<=E) return st[N];
int mid= (L+R)/2;
return max (query (2*N+1, L, mid, S, E), query(2*N+2, mid+1, R, S, E));
}
vector < pair <int, int> > tmp;
void update_dp_1 (int pos){
for (int i=0; i<checkpoints[pos-2].size(); i++){
int y= checkpoints[pos-2][i];
upd (0, 0, maxcord, y, y, dp_3[pos-2][i]);
}
tmp.clear();
for (pair <int, int> p:store[pos-1]){
tmp.push_back(p);
}
for (int i:checkpoints[pos]) tmp.push_back(make_pair(i,5*maxn));
sort(tmp.begin(), tmp.end());
int counter=0;
for (pair <int, int> p:tmp){
int y=p.first, w=p.second;
if (w<5*maxn) {
upd (0, 0, maxcord, 0, y-1, w);
}
else{
dp_1[pos][counter]= max(dp_1[pos][counter], query(0, 0, maxcord, 0, maxcord));
counter++;
}
}
for (int i=0; i<checkpoints[pos-2].size(); i++){
int y= checkpoints[pos-2][i];
upd (0, 0, maxcord, y, y, -dp_3[pos-2][i]);
}
for (pair <int, int> p:tmp){
int y=p.first, w=p.second;
if (w<5*maxn) upd (0, 0, maxcord, 0, y-1, -w);
}
}
void update_dp_2(int pos){
for (int i=0; i<checkpoints[pos-1].size(); i++){
int y= checkpoints[pos-1][i];
//if (pos==3) cout<<"upd "<<y<<" "<<y<<" --> "<<dp_1[pos-1][i]<<endl;
upd (0, 0, maxcord, y, y, dp_1[pos-1][i]);
}
tmp.clear();
for (pair <int, int> p:store[pos-1]) tmp.push_back(p);
for (int i:checkpoints[pos]) tmp.push_back(make_pair(i,5*maxn));
sort(tmp.begin(), tmp.end());
int counter=0;
for (pair <int, int> p:tmp){
int y= p.first, w= p.second;
if (w<5*maxn){
//if (pos==3) cout<<"upd "<<0<<" "<<y-1<<" --> "<<w<<endl;
upd (0, 0, maxcord, 0, y-1, w);
}
else{
// if (pos==3) cout<<"query "<<query(0, 0, maxcord, 0 , maxcord)<<endl;
dp_1[pos][counter]= max(dp_1[pos][counter], query(0, 0, maxcord, 0, maxcord));
counter++;
}
}
for (int i=0; i<checkpoints[pos-1].size(); i++){
int y= checkpoints[pos-1][i];
upd (0, 0, maxcord, y, y, -dp_1[pos-1][i]);
}
for (pair <int, int> p:tmp){
int y= p.first, w= p.second;
if (w<5*maxn){
upd (0, 0, maxcord, 0, y-1, -w);
}
}
}
void update_dp_3 (int pos){
for (int i=0; i<checkpoints[pos].size(); i++) dp_2[pos][i]= dp_1[pos][i];
int highest_checkpoint=0;
for (int i=0; i<checkpoints[pos-1].size(); i++){
int y= checkpoints[pos-1][i];
highest_checkpoint= max(highest_checkpoint, y);
upd(0, 0, maxcord, y, y, dp_2[pos-1][i]);
}
tmp.clear();
for (pair <int, int> p:store[pos]) tmp.push_back(p);
for (int i:checkpoints[pos]) tmp.push_back(make_pair(i,5*maxn));
sort(tmp.begin(), tmp.end());
reverse(tmp.begin(), tmp.end());
int counter= checkpoints[pos].size()-1;
for (pair <int, int> p:tmp){
int y= p.first, w=p.second;
if (w<5*maxn) {
upd(0, 0, maxcord, y, maxcord, w);
}
else{
if (pos>2) dp_2[pos][counter]= max(dp_2[pos][counter], query(0, 0, maxcord, 0, maxcord));
counter--;
}
}
for (int i=0; i<checkpoints[pos-1].size(); i++){
int y= checkpoints[pos-1][i];
upd(0, 0, maxcord, y, y, -dp_2[pos-1][i]);
}
for (pair <int, int> p:tmp){
int y= p.first, w=p.second;
if (w<5*maxn) upd(0, 0, maxcord, y, maxcord, -w);
}
}
void update_dp_4 (int pos){
tmp.clear();
for (pair<int,int> p:store[pos+1]) tmp.push_back(p);
for (int i:checkpoints[pos]) {
tmp.push_back(make_pair(i,5*maxn));
}
sort(tmp.begin(), tmp.end());
long long int cur_sum=0;
int counter=0;
for (pair <int, int> p:tmp){
int y=p.first, w=p.second;
if (w<5*maxn) cur_sum+=w;
else {
dp_3[pos][counter]= dp_2[pos][counter]+cur_sum;
counter++;
}
}
}
long long max_weights(int max_cord, int COUNT, std::vector<int> A, std::vector<int> B, std::vector<int> W){
n=COUNT;
maxcord=max_cord+2;
for (int i=1; i<=n; i++){
X[i]= A[i-1]+2;
Y[i]= B[i-1]+2;
weight[i]= W[i-1];
}
for (int i=1; i<=n; i++) store[X[i]].push_back(make_pair(Y[i], weight[i]));
for (int i=0; i<=maxcord; i++) sort(store[i].begin(), store[i].end());
for (int i=1; i<=n; i++){
if (Y[i]>1) checkpoints[X[i]].push_back(Y[i]-1);
}
for (int i=0; i<=maxcord; i++) {
checkpoints[i].push_back(0);
if (i>=2) checkpoints[i].push_back(maxcord);
}
for (int i=0; i<=maxcord; i++) sort(checkpoints[i].begin(), checkpoints[i].end());
for (int i=0; i<=maxcord; i++){
for (int j=0; j<checkpoints[i].size(); j++){
dp_1[i].push_back(0);
dp_2[i].push_back(0);
dp_3[i].push_back(0);
dp_4[i].push_back(0);
}
}
for (int i=2; i<=maxcord; i++){
update_dp_1(i);
update_dp_2(i);
update_dp_3(i);
update_dp_4(i);
}
return dp_3[maxcord][0];
}
