#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ff first
#define ss second
template<typename T> int sz(const T &x) { return x.size(); }
void maxs(ll &a, ll b) {
if (a < b) a = b;
}
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++) Y[i]++;
vector all(n, vector<int>{0});
for (int i = 0; i < m; i++) all[X[i]].emplace_back(Y[i]);
for (int i = 0; i < m; i++) all[X[i]].emplace_back(Y[i] - 1);
for (int i = 0; i < n; i++) {
sort(all[i].begin(), all[i].end());
if (all[i].back() != n) all[i].emplace_back(n);
}
for (int i = n - 1; i >= 0; i--) {
set<int> st;
for (int j = max(i - 2, 0); j <= i; j++) {
for (int x: all[j]) st.insert(x);
}
all[i].clear();
for (int x: st) all[i].emplace_back(x);
}
auto get = [&](int x, int y) -> int {
return upper_bound(all[x].begin(), all[x].end(), y) - all[x].begin() - 1;
};
vector<vector<ll>> pre(n);
for (int i = 0; i < n; i++) pre[i].assign(all[i].size(), 0ll);
for (int i = 0; i < m; i++) pre[X[i]][get(X[i], Y[i])] += W[i];
for (int i = 0; i < n; i++) {
for (int j = 1; j < pre[i].size(); j++) pre[i][j] += pre[i][j - 1];
}
vector<vector<pair<ll, ll>>> dp(n);
// dp[i][j] - birinchi i'ta qatorni hisobga osak ohirgi qatorni boyi j bosa max javob
// ff - o'zinikini qo'shilgan, ss - o'ziniki qo'shilmagan
for (int i = 0; i < n; i++) dp[i].assign(all[i].size(), make_pair(0ll, 0ll));
for (int i = 1; i < n; i++) {
// i > 0
ll mx = -1e18, mx2 = -1e18;
for (int j = 0, k = 0; j < dp[i].size() and i > 0; j++) {
while (k < sz(dp[i - 1]) and all[i - 1][k] <= all[i][j]) {
maxs(mx, dp[i - 1][k].ss - pre[i - 1][k]);
maxs(mx2, dp[i - 1][k].ff);
k++;
}
// cout << '\t' << i << ' ' << j << ' ' << k << ' ' << mx << endl;
// cout << '\t' << pre[i - 1][get(i - 1, all[i][j])] << ' ' << get(i - 1, all[i][j]) << endl;
maxs(dp[i][j].ss, max(mx + pre[i - 1][get(i - 1, all[i][j])], mx2));
}
mx = -1e18, mx2 = -1e18;
for (int j = sz(dp[i]) - 1, k = -2; j >= 0 and i > 0; j--) {
if (k == -2) k = sz(dp[i - 1]) - 1;
while (k >= 0 and all[i - 1][k] > all[i][j]) {
maxs(mx, dp[i - 1][k].ff + pre[i][get(i, all[i - 1][k])]);
maxs(mx2, dp[i - 1][k].ff);
k--;
}
maxs(dp[i][j].ff, mx - pre[i][j]);
maxs(dp[i][j].ss, mx2);
}
// i > 1
mx = -1e18;
for (int j = 0, k = 0; j < dp[i].size() and i > 1; j++) {
while (k < sz(dp[i - 2]) and all[i - 2][k] <= all[i][j]) {
maxs(mx, dp[i - 2][k].ff);
k++;
}
maxs(dp[i][j].ss, mx + pre[i - 1][get(i - 1, all[i][j])]);
}
mx = -1e18;
for (int j = sz(dp[i]) - 1, k = -2; j >= 0 and i > 1; j--) {
if (k == -2) k = sz(dp[i - 2]) - 1;
while (k >= 0 and all[i - 2][k] > all[i][j]) {
maxs(mx, dp[i - 2][k].ff + pre[i - 1][get(i - 1, all[i - 2][k])]);
k--;
}
maxs(dp[i][j].ss, mx);
}
// i > 2
if (i > 2) {
mx = -1e18;
for (int k = 0; k < sz(dp[i - 3]); k++) {
maxs(mx, dp[i - 3][k].ff + pre[i - 2][get(i - 2, all[i - 3][k])]);
}
for (int j = 0; j < sz(dp[i]); j++) {
maxs(dp[i][j].ss, mx + pre[i - 1][get(i - 1, all[i][j])]);
}
}
for (int j = 0; j < sz(dp[i]); j++) maxs(dp[i][j].ff, dp[i][j].ss);
// cout << i << endl;
// for (int j = 0; j < sz(dp[i]); j++) {
// cout << all[i][j] << ' ' << dp[i][j].ff << ' ' << dp[i][j].ss << endl;
// }
}
// for (int i = 1; i < n; i++) {
// ll mx = -1e18, mx2 = -1e18, mx3 = -1e18;
// for (int j = 0; j <= n; j++) {
// maxs(mx, dp[i - 1][j].ss - pre[i - 1][j]);
// maxs(mx2, dp[i - 1][j].ff);
// maxs(dp[i][j].ss, max(mx + pre[i - 1][j], mx2));
// if (i > 1) {
// maxs(mx3, dp[i - 2][j].ff);
// maxs(dp[i][j].ss, mx3 + pre[i - 1][j]);
// }
// }
// mx = -1e18;
// for (int j = 0; j <= n and i > 2; j++) {
// maxs(mx, dp[i - 3][j].ff + pre[i - 2][j]);
// }
// for (int j = 0; j <= n; j++) maxs(dp[i][j].ss, mx + pre[i - 1][j]);
// mx = -1e18, mx2 = -1e18, mx3 = -1e18;
// for (int j = n; j >= 0; j--) {
// maxs(dp[i][j].ff, mx - pre[i][j]);
// maxs(dp[i][j].ss, mx2);
// maxs(mx, dp[i - 1][j].ff + pre[i][j]);
// maxs(mx2, dp[i - 1][j].ff);
// if (i > 1) {
// maxs(mx3, dp[i - 2][j].ff + pre[i - 1][j]);
// maxs(dp[i][j].ss, mx3);
// }
// maxs(dp[i][j].ff, dp[i][j].ss);
// // maxlash esdan chiqmasin
// }
// }
ll ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < sz(dp[i]); j++) maxs(ans, dp[i][j].ff);
}
return ans;
}
// g++ -o fish -O2 fish.cpp grader.cpp -std=c++20 && .\fish < input.txt > output.txt
