#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back
ll dp[3005][3005][3]; // A(a), (A)a, (A)
ll pref[2][3005];
int pos[3005][3005];
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
for(int i=0;i<sz(x);i++) pos[x[i]+1][y[i]+1] = w[i];
memset(dp, -1, sizeof(dp));
ll ans = 0;
for(int i=1;i<=n;i++){
memset(pref, 0, sizeof(pref));
for(int j=1;j<=n;j++){
pref[0][j] = pref[0][j-1] + pos[i-1][j];
pref[1][j] = pref[1][j-1] + pos[i][j];
}
if(i == 1){
for(int j=0;j<=n;j++) dp[i][j][2] = 0;
}
else{
// 0
ll mx = -1e18;
for(int j=n;j>=0;j--){
if(dp[i-1][j][0] != -1) mx = max(mx, dp[i-1][j][0] + pref[1][j]);
if(dp[i-1][j][2] != -1) mx = max(mx, dp[i-1][j][2] + pref[1][j]);
dp[i][j][0] = max(dp[i][j][0], mx - pref[1][j]);
}
// 1
for(int j=n;j>=0;j--){
dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][0] + pref[1][j]);
dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][2] + pref[1][j]);
}
// 2
ll mx0 = -1e18, mx1 = -1e18;
for(int j=0;j<=n;j++){
if(dp[i-1][j][0] != -1) mx0 = max(mx0, dp[i-1][j][0]);
if(dp[i-1][j][1] != -1) mx1 = max(mx1, dp[i-1][j][1] - pref[0][j]);
if(dp[i-1][j][2] != -1) mx1 = max(mx1, dp[i-1][j][2] - pref[0][j]);
dp[i][j][2] = max(dp[i][j][2], mx0);
dp[i][j][2] = max(dp[i][j][2], mx1 + pref[0][j]);
}
}
ll sum = 0;
for(int j=0;j<=n;j++){
sum += pos[i+1][j];
ans = max(ans, dp[i][j][0] + sum);
ans = max(ans, dp[i][j][2] + sum);
}
}
return ans;
}
