#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const ll INF = 1e18;
const int MAXN = 2e5+5;
vector<pii>fish[MAXN];
vector<ll>dp[2][MAXN],crd[MAXN],pref[MAXN];
void chmax(ll &x,ll y){
x = max(x,y);
}
long long max_weights(int n, int m, vector<int> X, vector<int> Y,vector<int> W) {
ll ans = 0;
for(int i=0;i<m;i++)fish[X[i]].pb({Y[i],W[i]});
for(int i=0;i<n;i++)sort(all(fish[i]));
for(int i=0;i<n;i++){
for(pii z:fish[i])crd[i].pb(z.fi);
if(i)for(pii z:fish[i-1])crd[i].pb(z.fi);
if(i+1<n)for(pii z:fish[i+1])crd[i].pb(z.fi);
crd[i].pb(-1);
sort(all(crd[i]));
crd[i].resize(unique(all(crd[i])) - crd[i].begin());
int s = sz(crd[i]);
dp[0][i].assign(s,-INF);
dp[1][i].assign(s,-INF);
pref[i].assign(s,0);
for(pii z:fish[i]){
int p = lb(all(crd[i]),z.fi) - crd[i].begin();
pref[i][p] = z.se;
}
for(int j=1;j<s;j++)pref[i][j]+=pref[i][j-1];
}
//initialize column one
for(ll &x:dp[0][0])x = 0;
dp[1][0][sz(crd[0])-1] = 0;
for(int i=1;i<n;i++){
//last pier is lower
ll mx = -INF;
int ptr = -1;
for(int j=0;j<sz(crd[i]);j++){
while(ptr + 1 < sz(crd[i-1]) && crd[i-1][ptr+1] <= crd[i][j]){
ptr++;
chmax(mx,dp[0][i-1][ptr] - pref[i-1][ptr]);
}
chmax(dp[0][i][j],mx + pref[i-1][ptr]);
}
//;ast pier is higher
mx = -INF;
ptr = sz(crd[i-1]);
ll sum = pref[i].back();
vector<pii>f = fish[i];
for(int j=sz(crd[i])-1;j>=0;j--){
while(ptr - 1 >= 0 && crd[i-1][ptr-1] >= crd[i][j]){
ptr--;
while(!f.empty() && f.back().fi > crd[i-1][ptr]){
sum-=f.back().se;
f.pop_back();
}
chmax(mx,dp[1][i-1][ptr] + sum);
chmax(mx,dp[0][i-1][ptr] + sum);
}
chmax(dp[1][i][j],mx - pref[i][j]);
}
if(i>=1){
//i-1 column is empty :
//i-2 pier is shorter
sum = 0;
mx = -INF;
int ptr0 = -1; //column i-2
int ptr1 = -1; //column i-1
for(int j=0;j<sz(crd[i]);j++){
while(ptr0 + 1 < sz(crd[i-2]) && crd[i-2][ptr0+1] <= crd[i][j]){
ptr0++;
mx = max(mx,dp[0][i-2][ptr0]);
mx = max(mx,dp[1][i-2][ptr0]);
}
while(ptr1 + 1 < sz(fish[i-1]) && fish[i-1][ptr1+1].fi <= crd[i][j]){
ptr1++;
sum+=fish[i-1][ptr1].se;
}
chmax(dp[0][i][j],mx + sum);
}
//i-2 pier is higher
f = fish[i-1];
sum = pref[i-1].back();
mx = -INF;
ptr0 = sz(crd[i-2]);
ptr1 = sz(f) - 1;
for(int j=sz(crd[i])-1;j>=0;j--){
while(ptr0 - 1 >= 0 && crd[i-2][ptr0-1] >= crd[i][j]){
ptr0--;
while(ptr1 >= 0 && f[ptr1].fi > crd[i-2][ptr0]){
sum-=f[ptr1].se;
ptr1--;
}
chmax(mx,dp[0][i-2][ptr0] + sum);
chmax(mx,dp[1][i-2][ptr0] + sum);
}
chmax(dp[0][i][j],mx);
}
}
/*
cout<<"at "<<i<<'\n';
for(int x:crd[i])cout<<x<<" ";cout<<'\n';
for(ll x:dp[0][i])cout<<x<<" ";cout<<'\n';
for(ll x:dp[1][i])cout<<x<<" ";cout<<'\n';
* */
}
for(ll x:dp[0][n-1])ans = max(ans,x);
for(ll x:dp[1][n-1])ans = max(ans,x);
if(n>=2){
int ptr = -1;
ll sum = 0;
for(int i=0;i<sz(crd[n-2]);i++){
while(ptr + 1 < sz(fish[n-1]) && fish[n-1][ptr+1].fi <= crd[n-2][i]){
ptr++;
sum+=fish[n-1][ptr].se;
}
chmax(ans,dp[0][n-2][i]+sum);
chmax(ans,dp[1][n-2][i]+sum);
}
}
return ans;
}
