#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<long long>> nxt;
vector<vector<long long>> pre;
vector<vector<pair<int, int>>> in_col;
vector<vector<vector<long long>>> dp;
long long bt(int col, bool f, bool f2) {//is last bigger and does he need payment if he is not
if (col >= n) {
return 0;
}
long long& ret = dp[col][f][f2];
if (ret != -1) {
return ret;
}
ret = 0;
int sz = in_col[col].size();
if (f) {//last is bigger, (he paid for me)
long long s = 0;
for (int i = 0; i < sz; ++i) {
long long w = s;
if (col < n - 1) {
w += nxt[col][i];
}
ret = max(ret, bt(col + 1, 1, 0) + w); //I'm bigger than next
s -= in_col[col][i].second;//delete what I covered
}
//don't build anything..
ret = max(ret, bt(col + 1, 0, 0));//telling next not to pay for me or take from me
} else {//last is smaller, I pay for him if f2
long long s = 0;
for (int i = 0; i < sz; ++i) {
long long w = s;
if (f2) {
w += pre[col][i];
}
ret = max(ret, bt(col + 1, 0, 1) + w); //I'm smaller than next and I need payment (I'll subtract what I cover)
s -= in_col[col][i].second;
}
long long w = 0;
if (col < n - 1) {
w = nxt[col][sz - 1];
}
if (f2) {
w += pre[col][sz - 1];
}
ret = max(ret, bt(col + 1, 1, 0) + w); //full tower
}
//cout << "col, f, f2, ret: " << col << ' ' << f << ' ' << f2 << ' ' << ret << endl;
return ret;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
n = N;
in_col.resize(N);
for (int i = 0; i < M; ++i) {
in_col[X[i]].push_back({Y[i], W[i]});
}
for (int i = 0; i < N; ++i) {
sort(in_col[i].begin(), in_col[i].end());
in_col[i].push_back({N, 0});
}
pre.resize(N);
for (int col = 1; col < N; ++col) {
pre[col].resize(in_col[col].size());
for (int i = 0; i < (int) in_col[col].size(); ++i) {
int ptr = 0;
long long sum = 0;
while (ptr < (int) in_col[col - 1].size() && in_col[col - 1][ptr].first < in_col[col][i].first) {
sum += in_col[col - 1][ptr].second;
ptr++;
}
pre[col][i] = sum;
}
}
//cout << "PRE: " << pre[1][1] << endl;
nxt.resize(N);
for (int col = 0; col < N - 1; ++col) {
nxt[col].resize(in_col[col].size());
for (int i = 0; i < (int) in_col[col].size(); ++i) {
int ptr = 0;
long long sum = 0;
while (ptr < (int) in_col[col + 1].size() && in_col[col + 1][ptr].first < in_col[col][i].first) {
sum += in_col[col + 1][ptr].second;
ptr++;
}
nxt[col][i] = sum;
}
}
dp.resize(N);
for (int i = 0; i < N; ++i) {
dp[i].resize(2);
dp[i][0].assign(2, -1);
dp[i][1].assign(2, -1);
}
long long ans = bt(0, 0, 0);
return ans;
}
