#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 3e5 + 50;
const int N = 1e5 + 50;
const ll INF = 1e17;
ll dp[N][3][3];
vector<pair<int, int>> pts[N];
long long max_weights(int n, int m, vector<int> x, vector<int> y,
vector<int> w) {
for(int i = 0; i < m; i++) {
pts[x[i]].push_back({y[i], w[i]});
}
for(int i = 0; i <= n; i++) {
sort(pts[i].begin(), pts[i].end());
}
for(int f1 = 0; f1 < 3; f1++) {
for(int f2 = 0; f2 < 3; f2++) {
dp[n][f1][f2] = 0;
}
}
for(int i = n - 1; i >= 0; i--) {
// desc, desc
dp[i][0][0] = dp[i + 1][2][0];
ll sum = 0;
ll mxsum = -INF;
int ptr = 0;
for(int j = 0; j < (int)pts[i + 1].size(); j++) {
sum += pts[i + 1][j].second;
while(ptr < (int)pts[i].size() && pts[i][ptr].first <= pts[i + 1][j].first) sum -= pts[i][ptr++].second;
mxsum = max(mxsum, sum);
}
dp[i][0][0] = max(dp[i][0][0], mxsum + dp[i + 1][0][0]);
dp[i][0][0] = max(dp[i][0][0], mxsum + dp[i + 1][0][2]);
// asc, desc
dp[i][1][0] = dp[i + 1][2][0];
sum = 0;
mxsum = -INF;
ptr = 0;
for(int j = 0; j < (int)pts[i + 1].size(); j++) {
sum += pts[i + 1][j].second;
while(ptr < (int)pts[i].size() && pts[i][ptr].first <= pts[i + 1][j].first) sum -= pts[i][ptr++].second;
mxsum = max(mxsum, sum);
}
dp[i][1][0] = max(dp[i][1][0], dp[i + 1][0][0] + mxsum);
dp[i][1][0] = max(dp[i][1][0], dp[i + 1][0][2] + mxsum);
// asc, asc
dp[i][1][1] = dp[i + 1][2][1];
sum = 0;
for(int j = 0; j < (int)pts[i + 1].size(); j++) sum += pts[i + 1][j].second;
if(i > 0) for(int j = 0; j < (int)pts[i - 1].size(); j++) sum += pts[i - 1][j].second;
dp[i][1][1] = max(dp[i][1][1], sum + dp[i + 1][1][0]);
dp[i][1][1] = max(dp[i][1][1], sum + dp[i + 1][0][2]);
if(i > 0) {
sum = 0;
mxsum = -INF;
ptr = 0;
for(int j = 0; j < (int)pts[i - 1].size(); j++) {
sum += pts[i - 1][j].second;
while(ptr < (int)pts[i].size() && pts[i][ptr].first <= pts[i - 1][j].first) sum -= pts[i][ptr++].second;
mxsum = max(mxsum, sum);
}
dp[i][1][1] = max(dp[i][1][1], mxsum + dp[i + 1][1][1]);
sum = 0;
for(int j = 0; j < (int)pts[i - 1].size(); j++) {
sum += pts[i - 1][j].second;
}
dp[i][1][1] = max(dp[i][1][1], sum + dp[i + 1][1][2]);
}
// null, desc
dp[i][2][0] = dp[i + 1][2][1];
sum = 0;
for(int j = 0; j < (int)pts[i + 1].size(); j++) {
sum += pts[i + 1][j].second;
}
dp[i][2][0] = max(dp[i][2][0], dp[i + 1][1][0] + sum);
dp[i][2][0] = max(dp[i][2][0], dp[i + 1][0][2] + sum);
// null, asc
dp[i][2][1] = dp[i + 1][2][1];
sum = 0;
if(i > 0) for(int j = 0; j < (int)pts[i - 1].size(); j++) sum += pts[i - 1][j].second;
for(int j = 0; j < (int)pts[i + 1].size(); j++) sum += pts[i + 1][j].second;
dp[i][2][1] = max(dp[i][2][1], sum + dp[i + 1][1][0]);
dp[i][2][1] = max(dp[i][2][1], sum + dp[i + 1][0][2]);
if(i > 0) {
sum = 0;
mxsum = -INF;
ptr = 0;
for(int j = 0; j < (int)pts[i - 1].size(); j++) {
sum += pts[i - 1][j].second;
while(ptr < (int)pts[i].size() && pts[i][ptr].first <= pts[i - 1][j].first) sum -= pts[i][ptr++].second;
mxsum = max(mxsum, sum);
}
//if(i == 1) printf("mxsum je %lld\n", mxsum);
dp[i][2][1] = max(dp[i][2][1], mxsum + dp[i + 1][1][1]);
sum = 0;
for(int j = 0; j < (int)pts[i - 1].size(); j++) {
sum += pts[i - 1][j].second;
}
dp[i][2][1] = max(dp[i][2][1], sum + dp[i + 1][1][2]);
}
dp[i][0][2] = max(dp[i + 1][2][0], dp[i + 1][1][2]);
dp[i][1][2] = max(dp[i + 1][2][1], dp[i + 1][1][2]);
/*for(int f1 = 0; f1 < 3; f1++)
for(int f2 = 0; f2 < 3; f2++)
printf("dp[%d][%d][%d] -> %lld\n", i, f1, f2, dp[i][f1][f2]);
printf("----------------------------------\n");*/
}
ll sol = -INF;
for(int f1 = 0; f1 < 3; f1++) {
for(int f2 = 0; f2 < 3; f2++)
sol = max(sol, dp[0][f1][f2]);
}
return sol;
}
