#include "fish.h"
#include <bits/stdc++.h>
#define ent '\n'

using namespace std;
typedef long long ll;
const int maxn = 3e3 + 12;

vector<pair<int, int>> g[maxn];
ll dp[maxn][maxn], dpt[maxn][maxn], d[maxn][maxn];
ll pref[maxn][maxn], mx[maxn][maxn], suff[maxn][maxn];
ll a[maxn][maxn], mval[maxn][maxn], sufft[maxn][maxn];

long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    ll ans = 0;
    for(int i=0;i<m;i++){
        x[i]++, y[i]++;
        a[x[i]][y[i]] += w[i];
    }
    for(int i=0;i<=n;i++){
        for(int x=0;x<=n;x++){
            dp[i][x] = d[i][x] = dpt[i][x] = -1e18;
        }
    }
    dp[0][0] = d[0][0] = dpt[0][0] = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            pref[i][j] = pref[i][j-1] + a[i][j];
        }

        for(int x=0;x<=n;x++){
            dp[i][x] = max(mx[i-1][x] + pref[i-1][x], mval[i-1][x]);
            d[i][x] = max(dp[i][x], suff[i-1][x] - pref[i][x]);
            dpt[i][x] = d[i-1][x] + pref[i][x];
            mval[i][x] = d[i][x];
            if(x > 0) mval[i][x] = max(mval[i][x-1], d[i][x]);
            ans = max(ans, d[i][x]);
        }

        for(int x=0;x<=n;x++){
            mx[i][x] = max(dp[i][x], d[i][x]) - pref[i][x];
            if(x > 0) mx[i][x] = max(mx[i][x], mx[i][x-1]);
        }
        for(int x=n;x>=0;x--){
            suff[i][x] = max(suff[i][x+1], d[i][x] + pref[i+1][x]);
        }
    }
    return ans;
}