#include "fish.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <map>
#include <queue>
#define ll long long
using namespace std;
vector <array<ll, 2>> V[100000];
vector <ll> pre;
vector <array<ll, 3>> dp[100000];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
ll f = -1e18, j, k, l, s = 0, t = 0, v, x, u, p = -1e18, mx, mx2, cur;
map <ll, ll> mp;
for (int i=0; i<M; ++i) {
V[X[i]].push_back({Y[i], W[i]});
}
for (int i=0; i<N; ++i) {
sort(V[i].begin(), V[i].end());
}
j = 0;
s = 0;
for (auto [y, w] : V[1]) {
s += w;
dp[0].push_back({y, 0, (ll)-1e18});
f = max(f, s);
}
for (int i=1; i<N; ++i) {
if (i >= 3) {
j = 0;
s = 0;
for (auto [y, w, a] : dp[i-3]) {
w = max(w, a);
while (j < V[i-2].size() && V[i-2][j][0] <= y) {
s += V[i-2][j][1];
++j;
}
p = max(p, s+w);
}
}
mp.clear();
mx = mx2 = -1e18, s = 0;
if (i >= 2) {
j = 0;
for (auto [y, w, a] : dp[i-2]) {
w = max(w, a);
while (j < V[i-1].size() && V[i-1][j][0] <= y) {
s += V[i-1][j][1];
++j;
}
mx = max(mx, w);
mx2 = max(mx2, w+s);
}
}
for (auto [y, w] : V[i-1]) {
++mp[y];
}
if (i != N-1) {
for (auto [y, w] : V[i+1]) {
++mp[y];
}
}
s = j = k = t = 0;
v = x = -1e18;
pre.clear();
for (auto [y, w, a] : dp[i-1]) {
while (j < V[i].size() && V[i][j][0] <= y) {
s += V[i][j][1];
++j;
}
while (k < V[i-1].size() && V[i-1][k][0] <= y) {
t += V[i-1][k][1];
++k;
}
v = max(v, max(w, a)+s);
x = max(x, w-t);
}
s = j = k = t = l = u = 0;
for (auto [y, z] : mp) {
while (j < V[i].size() && V[i][j][0] <= y) {
s += V[i][j][1];
++j;
}
while (k < V[i-1].size() && V[i-1][k][0] <= y) {
t += V[i-1][k][1];
++k;
}
while (i != N-1 && l < V[i+1].size() && V[i+1][l][0] <= y) {
u += V[i+1][l][1];
++l;
}
cur = max(max(t, p+t), max(mx2, mx+t));
//cout << v << " " << x << " " << s << " " << t << endl;
//cout << cur << endl;
cur = max(cur, x+t);
//cout << cur << endl;
dp[i].push_back({y, cur, v-s});
//cout << i << " " << y << " " << cur << "/" << v-s << endl;
cur = max(cur, v-s);
f = max(f, cur + u);
}
}
return f;
}
