#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=1e6+5;

vector<int> col[MX];
ll dp[MX][2], pref[MX], dq[MX];

vector<int> Y;

int getPos(int c, int p) {
        if(p>=Y[col[c].back()]) return col[c].size();

        int l=0,r=col[c].size()-1,res=-1;
        while(l<=r) {
                int m=(l+r)/2;
                if(Y[col[c][m]]>=p) {
                        res=m,r=m-1;
                } else {
                        l=m+1;
                }
        }

        return res;
}

ll sum(ll c, ll x, ll y) {
        if(col[c].empty()) return 0;

        int l=getPos(c,x)-1, r=getPos(c,y+1)-1;
        if(r<0) return 0;

        ll res=pref[col[c][r]];
        if(l>=0) res-=pref[col[c][l]];
        return res;
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {

        set<pair<int,int>> pts;
        for(int i=0;i<M;i++) {
                pts.insert({X[i],Y[i]});
        }

        for(int i=0;i<M;i++) {
                if(X[i]>0 && !pts.count({X[i]-1,Y[i]})) {
                        pts.insert({X[i]-1,Y[i]});
                        X.push_back(X[i]-1);
                        Y.push_back(Y[i]);
                        W.push_back(0);
                }
                if(X[i]+1<N && !pts.count({X[i]+1,Y[i]})) {
                        pts.insert({X[i]+1,Y[i]});
                        X.push_back(X[i]+1);
                        Y.push_back(Y[i]);
                        W.push_back(0);
                }
        }

        M=X.size();
        for(int i=0;i<M;i++) {
                col[X[i]].push_back(i);
        }
        ::Y=Y;

        for(int i=0;i<N;i++) {
                sort(col[i].begin(),col[i].end(),[&](int i, int j){
                        return Y[i]<Y[j];
                });

                for(int j=0;j<col[i].size();j++) {
                        pref[col[i][j]]+=W[col[i][j]];
                        if(j>0) pref[col[i][j]]+=pref[col[i][j-1]];
                }
        }
        
        for(int i=0;i<N;i++) {
                if(i>=1) {
                        priority_queue<pair<ll,ll>> lf,rg;
                        for(auto j:col[i-1]) {
                                rg.push({
                                        max(dp[j][0],dp[j][1])+sum(i,-1,Y[j]),Y[j]});
                        }
                        int pt=0;
                        for(auto j:col[i]) {
                                while(rg.size() && rg.top().second<=Y[j]) rg.pop();

                                while(pt<col[i-1].size() && Y[col[i-1][pt]]<=Y[j]) {
                                        lf.push({dp[col[i-1][pt]][0]+sum(i-1,Y[col[i-1][pt]]+1,N),Y[j]});
                                        pt++;   
                                }

                                if(rg.size()) dp[j][1]=rg.top().first-sum(i,-1,Y[j]);
                                if(lf.size()) dp[j][0]=lf.top().first-sum(i-1,Y[j]+1,N); 

                                dp[j][0]=max(dp[j][0],sum(i-1,-1,Y[j]));
                        }
                }
                

                if(i>=2) {
                        priority_queue<pair<ll,ll>> lf,rg;
                        for(int j=0;j<col[i-2].size();j++) {
                                rg.push({max(dp[col[i-2][j]][0],dp[col[i-2][j]][1])+sum(i-1,-1,Y[col[i-2][j]]) 
                                        ,Y[col[i-2][j]]});
                        }
                        int pt=0;
                        for(auto j:col[i]) {
                                while(rg.size() && rg.top().second<=Y[j]) rg.pop();

                                while(pt<col[i-2].size() && Y[col[i-2][pt]]<=Y[j]) {
                                        lf.push({max(dp[col[i-2][pt]][0],dp[col[i-2][pt]][1]), 
                                                Y[col[i-2][pt]]});
                                        pt++;   
                                }

                                if(rg.size()) dp[j][0]=max(dp[j][0],rg.top().first);
                                if(lf.size()) dp[j][0]=max(dp[j][0],lf.top().first+sum(i-1,-1,Y[j]));

                                dp[j][0]=max(dp[j][0],dq[i-2]+sum(i-1,-1,Y[j]));
                                dq[i+1]=max(dq[i+1],dp[j][0]+sum(i+1,-1,Y[j]));
                        }
                }

                for(auto j:col[i]) {
                        dq[i+1]=max(dq[i+1],dp[j][0]+sum(i+1,-1,Y[j]));
                        dq[i+1]=max(dq[i+1],dp[j][1]+sum(i+1,-1,Y[j]));
                }
        }

        return *max_element(dq,dq+MX);
}