#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define chmax(a, b) a = max(a, b)
const int maxn = 3030;
ll a[maxn][maxn];
ll b[maxn][maxn]; ll t[maxn][maxn];
ll c[maxn];
ll pre[maxn][maxn];
ll get(int x, int l, int r) {
if (l>r) return 0;
return pre[x][r] - pre[x][l-1];
}
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++) pre[X[i]][Y[i] + 1] = W[i];
for (int x = 0; x < N; x++) for (int y = 1; y <= N; y++) pre[x][y] += pre[x][y-1];
c[1] = get(1, 1, N);
FOR(i, 1, N) a[1][i] = get(0, 1, i);
FOR(i, 1, N) b[1][i] = max(get(0, 1, i), get(1, i+1, N));
FOR(i, 2, N-1) {
FOR(j, 1, N) {
chmax(a[i][j], a[i-1][j]);
chmax(a[i][j], a[i][j-1] + get(i-1, j, j));
chmax(a[i][j], c[i-2] + get(i-1, 1, j));
}
FOR(j, 1, N) {
// FOR(k, 1, j) chmax(b[i][j], get(i-1, 1, j) + max(a[i-2][k], b[i-2][k]));
chmax(b[i][j], b[i][j-1] + get(i-1, j, j));
chmax(b[i][j], max(a[i-2][j], b[i-2][j]) + get(i-1, 1, j));
chmax(b[i][j], c[i-2] + get(i-1, 1, j));
chmax(b[i][j], a[i-1][j]);
chmax(b[i][j], b[i][j-1] + get(i-1, j, j));
}
t[i][N] = b[i-1][N];
for (int j=N-1; j>=1; j--) {
chmax(t[i][j], b[i-1][j]);
chmax(t[i][j], t[i][j+1] + get(i, j+1, j+1));
}
FOR(j, 1, N) chmax(b[i][j], t[i][j]);
c[i] = c[i-1];
FOR(j, 1, N) chmax(c[i], get(i, 1, j) + max(a[i-1][j], b[i-1][j]));
}
ll ans = c[N-1];
FOR(i, 1, N) chmax(ans, a[N-1][i]);
FOR(i, 1, N) chmax(ans, b[N-1][i]);
// cout << b[3][4] << endl;
return ans;
}
