#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using ll = long long;
int n, m;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
n = N; m = M;
bool f = true, s = true, t = true;
for(int i = 0; i < m; i++) {
if(X[i] & 1) f = false;
if(X[i] > 1) s = false;
if(Y[i] != 0) t = false;
}
if(f) {
ll ans = 0;
for(int i = 0; i < m; i++) ans += W[i];
return ans;
}
if(s) {
ll f1 = 0, s1 = 0;
vector<ll> pref(n+1);
for(int i = 0; i < m; i++) {
if(X[i] == 0) f1 += W[i];
else s1 += W[i];
}
if(n <= 2) return max(f1, s1);
vector<ll> pref1(n+1), pref2(n+1);
for(int i = 0; i < m; i++) {
if(X[i] == 0) pref1[Y[i]] += W[i];
else pref2[Y[i]] += W[i];
}
ll ans = max(f1, s1);
for(int i = 1; i <= n; i++) {
pref1[i] += pref1[i-1];
pref2[i] += pref2[i-1];
}
for(int i = 0; i < n; i++) {
ans = max(ans, s1-pref2[i]+pref1[i]);
}
return ans;
}
vector<ll> pref1(n+1), pref2(n+1);
vector<vector<array<ll, 2>>> adj(n+1);
for(int i = 0; i < m; i++) {
adj[X[i]].push_back({Y[i]+1, W[i]});
if(X[i] == 0) pref1[Y[i]+1] += W[i];
if(X[i] == 1) pref2[Y[i]+1] += W[i];
}
for(int i = 2; i <= n; i++) {
pref1[i] += pref1[i-1];
pref2[i] += pref2[i-1];
}
vector<vector<array<ll, 2>>> dp(n+1, vector<array<ll, 2>>(n+1));
ll ans = 0;
for(int j = 0; j <= n; j++) {
for(int k = 0; k <= n; k++) {
if(k > j) {
dp[1][j][1] = max({dp[1][j][1], pref2[k]-pref2[j]});
}
else if(k < j){
dp[1][j][0] = max(dp[1][j][0], pref1[j]-pref1[k]);
dp[1][j][1] = max(dp[1][j][1], pref1[j]-pref1[k]);
}
}
ans = max({ans, dp[1][j][0], dp[1][j][1]});
}
for(int i = 2; i < n; i++) {
swap(pref1, pref2);
for(int j = 0; j <= n; j++) pref2[j] = 0;
for(auto [y, w] : adj[i]) pref2[y] = w;
for(int j = 1; j <= n; j++) pref2[j] += pref2[j-1];
for(int j = 0; j <= n; j++) {
for(int k = 0; k <= n; k++) {
if(k == j) continue;
if(k > j) {
dp[i][j][1] = max({dp[i][j][1], dp[i-1][k][1] + pref2[k] - pref2[j],
dp[i-1][k][0] + pref2[k] - pref2[j]});
}
else {
dp[i][j][0] = max({dp[i][j][0],
dp[i-1][k][0]+pref1[j]-pref1[k]});
}
}
ans = max({ans, dp[i][j][0], dp[i][j][1]});
}
}
return ans;
}
//int main()
//{
// cout << max_weights(4, 3, {0, 1, 2}, {0, 1, 2}, {1, 1, 1});
//}
