#include "fish.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define all(x) begin(x),end(x)
vector<vector<pair<ll, ll>>> fishAtX;
vector<vector<pair<ll, ll>>> fishWeightSum;
ll weightSum(ll x, ll y) {
if (x < 0 || x >= (ll)fishWeightSum.size())
return 0;
ll w = 0;
for (auto [fy, fw] : fishAtX[x])
if (fy <= y)
w += fw;
return w;
//ll idx = lower_bound(all(fishWeightSum[x]), make_pair(y, LLONG_MIN)) - fishWeightSum[x].begin();
//if (fishWeightSum[x][idx].first > y)
// idx--;
//return fishWeightSum[x][idx].second;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
if (M == 0) return 0;
vector<pair<ll, ll>> piers;
vector<tuple<ll, ll, ll>> fish;
for (ll i = 0; i < M; i++) {
fish.emplace_back(X[i], Y[i], W[i]);
if (X[i] != 0)
piers.emplace_back(X[i] - 1, Y[i]);
if (X[i] != N - 1)
piers.emplace_back(X[i] + 1, Y[i]);
}
sort(all(piers));
piers.erase(unique(all(piers)), piers.end());
fishAtX.resize(N);
for (ll i = 0; i < M; i++)
fishAtX[X[i]].emplace_back(Y[i], W[i]);
sort(all(fish));
fishWeightSum.resize(N);
for (ll i = 0; i < N; i++) {
fishWeightSum[i].emplace_back(LLONG_MIN, 0);
}
for (auto [x, y, w] : fish) {
fishWeightSum[x].emplace_back(y, fishWeightSum[x].back().second + w);
}
for (ll i = 0; i < N; i++) {
fishWeightSum[i].emplace_back(LLONG_MAX, fishWeightSum[i].back().second);
}
vector<array<ll, 2>> dpv(piers.size() + 1);
array<ll, 2>* dp = &dpv[1];
for (ll lp = (ll)piers.size() - 1; lp >= -1; lp--) {
ll cx = lp == -1 ? -5 : piers[lp].first;
ll cy = lp == -1 ? -5 : piers[lp].second;
//ll x1ShortFirstIdx = lower_bound(all(piers), make_pair(cx + 1, LLONG_MIN)) - piers.begin();
//ll x1LongFirstIdx = lower_bound(all(piers), make_pair(cx + 1, cy)) - piers.begin();
//ll x2FirstIdx = lower_bound(all(piers), make_pair(cx + 2, LLONG_MIN)) - piers.begin();
for (ll allowNext = 0; allowNext < 2; allowNext++) {
ll ans = 0;
for (ll np = lp + 1; np < (ll)piers.size(); np++) {
auto [nx, ny] = piers[np];
if (nx == cx + 1) {
if (allowNext) {
if (ny <= cy) {
ans = max(ans, dp[np][0]
+ weightSum(nx + 1, ny)
- weightSum(nx, ny)
);
} else {
ans = max(ans, dp[np][1]
+ weightSum(nx + 1, ny)
+ weightSum(nx - 1, ny)
- weightSum(cx, cy)
- weightSum(cx + 1, cy)
);
}
}
} else if (nx == cx + 2) {
if (ny <= cy) {
ans = max(ans, dp[np][1] + weightSum(nx + 1, ny));
} else {
ans = max(ans, dp[np][1]
+ weightSum(nx + 1, ny)
+ weightSum(nx - 1, ny)
- weightSum(cx + 1, cy)
);
}
} else if (nx > cx + 2) {
ans = max(ans, dp[np][1] + weightSum(nx + 1, ny) + weightSum(nx - 1, ny));
}
}
dp[lp][allowNext] = ans;
}
}
return dp[-1][1];
}
