#include "fish.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 100005;
vector<pair<int, int>> Y[N];
int c[N];
vector<ll> D[N], F[N];
ll E[N];
ll max_weights(int n, int m, vector<int> x, vector<int> y,
vector<int> w) {
for (int i = 0; i < m; i++)
Y[x[i]].emplace_back(y[i], w[i]);
for (int i = 0; i < n; i++)
sort(Y[i].begin(), Y[i].end()), c[i] = Y[i].size();
// initialize column 0:
E[0] = 0;
F[0].resize(c[0], -(ll)1e18);
D[0].resize(c[0]);
if (c[0]) {
D[0][0] = Y[0][0].second;
for (int j = 1; j < c[0]; j++) {
D[0][j] = D[0][j - 1] + Y[0][j].second;
}
}
// begin dp:
for (int i = 1; i < n; i++) {
//cout << "begin " << i << '\n';
E[i] = E[i - 1];
for (int j = 0; j < c[i - 1]; j++)
E[i] = max(max(E[i], D[i - 1][j]), F[i - 1][j]);
//cout << "E[i] " << E[i] << '\n';
if (!c[i]) continue;
D[i].resize(c[i]);
F[i].resize(c[i]);
vector<ll> below(c[i]), above(c[i]);
// compute below
int z = 0;
ll bestfound = -(ll)1e18;
for (int k = 0; k < c[i]; k++) {
while (z < c[i - 1] && Y[i - 1][z].first < Y[i][k].first) {
bestfound = max(bestfound, D[i - 1][z]);
z++;
}
below[k] = bestfound;
}
// compute above
z = c[i - 1] - 1;
bestfound = -(ll)1e18;
for (int k = c[i] - 1; k >= 0; k--) {
while (z >= 0 && Y[i - 1][z].first > Y[i][k].first) {
bestfound = max(bestfound, F[i - 1][z]);
z--;
}
above[k] = bestfound;
}
// compute D:
ll bestF = -(ll)1e18;
if (c[i - 1])
bestF = *max_element(F[i - 1].begin(), F[i - 1].end());
D[i][0] = max(max(below[0], E[i - 1]), bestF) + Y[i][0].second;
for (int j = 1; j < c[i]; j++) {
D[i][j] = max(below[j], D[i][j - 1]) + Y[i][j].second;
}
// compute F:
F[i][c[i] - 1] = max(E[i - 1], above[c[i] - 1]) + Y[i][c[i] - 1].second;
for (int j = c[i] - 2; j >= 0; j--) {
F[i][j] = max(above[j], F[i][j + 1]) + Y[i][j].second;
}
/*
for (int j = 0; j < c[i]; j++) {
cout << "D[i][" << j << "] " << D[i][j] << '\n';
}
for (int j = 0; j < c[i]; j++) {
cout << "F[i][" << j << "] " << F[i][j] << '\n';
}
*/
}
ll result = E[n - 1];
for (int j = 0; j < c[n - 1]; j++) {
result = max(result, F[n - 1][j]);
}
return result;
}
