#include "fish.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;
#define dbg(x) cerr<<#x<<": "<<x<<"\n";
/*
ValeNotta lover
*/
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<long long>>dp(N+2, vector<long long>(N+2)), vm(N+2, vector<long long>(N+2));
vector<vector<long long>>val(N+2, vector<long long>(N+2));
for(int i=0 ; i<M ; i++){
X[i]++; Y[i]++;
// swap(X[i], Y[i]);
val[X[i]][Y[i]]=W[i];
}
for(int i=1 ; i<=N ; i++){
for(int j=1 ; j<=N ; j++){
vm[i][j]+=val[i][j]+vm[i][j-1];
// cout<<vm[i][j]<<" ";
}
// cout<<"\n";
}
for(int i=1 ; i<=N+1 ; i++){
long long sum=0;
for(int j=0 ; j<=N ; j++){
sum+=val[i][j];
long long tequieronotta=0;
if(i<=N) dp[i][j]+=val[i-1][j];
// dp[i][j]=vm[i][j];
dp[i][j+1]=dp[i][j];
long long aux=dp[i][j];
for(int k=0 ; k<=N ; k++){
tequieronotta+=val[i-1][k];
long long uwu=vm[i-1][min(j, k)];
// if(k<=j) uwu=tequieronotta;
// else uwu=sum;
dp[i][j]=max(dp[i][j], aux+dp[i-1][k]-uwu);
}
}
}
long long ans=0;
for(int i=1 ; i<=N+1 ; i++){
for(int j=1 ; j<=N ; j++) ans=max(ans, dp[i][j]);
// cout<<"\n";
}
return ans;
}
