// komak!
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn5 = 3e5 + 10;
vector <pair<int, ll>> av[maxn5];
vector <ll> ps[maxn5], dp[maxn5][2];
long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y,
std::vector<int> w) {
for(int i = 0; i < m; i++){
av[x[i]].pb({y[i], w[i]});
}
for(int i = 0; i < n; i++){
av[i].pb({n, 0});
sort(all(av[i]));
ps[i].resize(int(av[i].size()));
ps[i][0] = av[i][0].se;
for(int j = 1; j < int(av[i].size()); j++){
ps[i][j] = ps[i][j - 1] + av[i][j].se;
}
dp[i][0].resize(int(av[i].size()));
dp[i][1].resize(int(av[i].size()));
}
ll ans = 0;
for(int i = 0; i < int(av[0].size()); i++){
dp[0][0][i] = (i ? -ps[0][i - 1] : 0);
int pt = upper_bound(all(av[1]), mp(av[0][i].fi - 1, mod)) - av[1].begin() - 1;
dp[0][1][i] = (pt >= 0 ? ps[1][pt] : 0);
if(i)
dp[0][0][i] = max(dp[0][0][i - 1], dp[0][0][i]);
}
for(int i = int(av[0].size()) - 2; i >= 0; i--)
dp[0][1][i] = max(dp[0][1][i], dp[0][1][i + 1]);
for(int i = 1; i < n; i++){
ll keepmx = ans;
for(int j = 0; j < int(av[i].size()); j++){
//debug(i);
//debug(j);
//debug(av[i][j].fi);
int pt = upper_bound(all(av[i - 1]), mp(av[i][j].fi - 1, mod)) - av[i - 1].begin() - 1;
dp[i][0][j] = keepmx;
if(pt >= 0)
dp[i][0][j] = max(dp[i][0][j], dp[i - 1][0][pt] + ps[i - 1][pt]);
//debug(dp[i][0][j]);
//debug(pt);
ans = max(ans, dp[i][0][j]);
dp[i][1][j] = max(keepmx, dp[i][0][j]);
dp[i][0][j] += (j ? -ps[i][j - 1] : 0);
if(j)
dp[i][0][j] = max(dp[i][0][j - 1], dp[i][0][j]);
pt = upper_bound(all(av[i - 1]), mp(av[i][j].fi, mod)) - av[i - 1].begin();
if(pt < int(av[i - 1].size())){
////debug(dp[i - 1][1][pt]);
dp[i][1][j] = max(dp[i][1][j], dp[i - 1][1][pt] - (j ? ps[i][j - 1] : 0));
}
//debug(dp[i][1][j]);
//debug(pt);
ans = max(ans, dp[i][1][j]);
if(i < n - 1){
pt = upper_bound(all(av[i + 1]), mp(av[i][j].fi - 1, mod)) - av[i + 1].begin() - 1;
dp[i][1][j] += (pt >= 0 ? ps[i + 1][pt] : 0);
//debug(pt);
}
}
for(int j = int(av[i].size()) - 2; j >= 0; j--)
dp[i][1][j] = max(dp[i][1][j], dp[i][1][j + 1]);
}
return ans;
}
