#include <bits/stdc++.h>
using namespace std;
long long pref[3002][3001], dp[3002][3001][2];
void chmax(long long& a, long long b) { a = max(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++) {
pref[X[i]][Y[i] + 1] += W[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
pref[i][j+1] += pref[i][j];
}
}
memset(dp, -0x3f, sizeof dp);
dp[n][0][0] = dp[n][0][1] = 0;
long long ans = 0;
for (int i = n-1; i >= 0; i--) {
long long mx1 = 0, mx2 = 0;
for (int j = n; j >= 0; j--) {
chmax(mx1, max(dp[i+1][j][0], dp[i+1][j][1]) + pref[i][j]);
chmax(mx2, max(dp[i+2][j][0], dp[i+2][j][1]) + pref[i+1][j]);
chmax(dp[i][j][0], mx1 - pref[i][j]);
chmax(dp[i][j][1], mx2);
}
mx1 = mx2 = 0;
for (int j = 0; j <= n; j++) {
chmax(mx1, dp[i+1][j][1] - pref[i+1][j]);
chmax(mx2, max(dp[i+2][j][0], dp[i+2][j][1]));
chmax(dp[i][j][1], mx1 + pref[i+1][j]);
chmax(dp[i][j][1], mx2 + pref[i+1][j]);
ans = max(ans, max(dp[i][j][0], dp[i][j][1]));
}
}
return ans;
}
// int main() {
// int n = 5;
// vector<int> X{0, 1, 4, 3};
// vector<int> Y{2, 1, 4, 3};
// vector<int> W{5, 2, 1, 3};
// int m = X.size();
// cout << max_weights(n, m, X, Y, W);
// for (int i = 0; i < m; i++)
// cout << "\n" << X[i] << " " << Y[i] << " " << W[i];
// }
