#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
vector< pair< int , int > > grid[N];
vector< long long > dp[N][2] , cur[N][2];
vector< long long > sum[N];
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++){
grid[X[i]].push_back(make_pair(Y[i] , W[i]));
}
for(int i = 0 ;i < N;i++){
sort(grid[i].begin(),grid[i].end());
for(int j = 0 ;j < (int)grid[i].size();j++){
sum[i].push_back(grid[i][j].second);
if(j)
sum[i][j] += sum[i][j - 1];
}
dp[i][0].resize((int)grid[i + 1].size() + 1);
dp[i][1].resize((int)grid[i + 1].size());
}
for(int i = 0 ;i < N;i++){
cur[i][0].resize((int)grid[i].size());
cur[i][1].resize((int)grid[i].size());
for(int j = 0 ;j < (int)grid[i].size();j++){
cur[i][0][j] = (long long)grid[i][j].second;
if(i > 0)
cur[i][0][j] = max(cur[i][0][j] , grid[i][j].second + dp[i - 1][0][j]);
if(j > 0)
cur[i][0][j] = max(cur[i][0][j] , grid[i][j].second + cur[i][0][j - 1]);
}
for(int j = (int)grid[i].size() - 1;j >= 0;j--){
if(i == 0){
cur[i][1][j] = -(long long)1e18;
continue;
}
cur[i][1][j] = sum[i][j] + dp[i - 1][1][j];
if(j < (int)grid[i].size() - 1)
cur[i][1][j] = max(cur[i][1][j] , cur[i][1][j + 1]);
}
for(int k = -1 , last , j = 0 ;j < (int)dp[i][0].size();j++){
last = (j == (int)grid[i + 1].size() ? N : grid[i + 1][j].first - 1);
while(k + 1 < (int)grid[i].size() && grid[i][k + 1].first <= last) k++;
dp[i][0][j] = (i == 0 ? 0 : dp[i - 1][0][(int)grid[i].size()]);
if(k != -1)
dp[i][0][j] = max(dp[i][0][j] , cur[i][0][k]);
if(k + 1 < (int)grid[i].size())
dp[i][0][j] = max(dp[i][0][j] , cur[i][1][k + 1]);
}
for(int k = (int)grid[i].size(), last , j = (int)dp[i][1].size() - 1;j >= 0;j--){
last = grid[i + 1][j].first + 1;
while(k - 1 >= 0 && grid[i][k - 1].first >= last)
k--;
dp[i][1][j] = (i == 0 ? 0 : dp[i - 1][0][(int)grid[i].size()]);
if(k < (int)grid[i].size())
dp[i][1][j] = max(dp[i][1][j] , cur[i][1][k] - (k == 0 ? 0 : sum[i][k - 1]));
}
}
long long ans = dp[N - 2][0][(int)grid[N - 1].size()];
for(int j = 0 ;j < (int)grid[N - 1].size();j++){
ans = max(ans , sum[N - 1][j] + dp[N - 2][1][j]);
}
return ans;
}
