#include "fish.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 12;

vector<pair<int, int>> g[maxn];
ll dp[322][322][322], pref[2022][2022];
ll a[2022][2022];

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 x=0;x<=n;x++){
            for(int y=0;y<=n;y++){
                dp[i][x][y] = -1e18;
            }
        }
    }
    dp[0][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 l=0;l<=min(n, 8);l++){
            for(int x=0;x<=min(n, 8);x++){
                for(int y=0;y<=min(n, 8);y++){
                    ll val = dp[i-1][l][x];
                    ans = max(ans, val);
                    if(x > y) val += pref[i][x] - pref[i][y];
                    if(max(l, x) < y) val += pref[i-1][y] - pref[i-1][max(l, x)];
                    dp[i][x][y] = max(dp[i][x][y], val);
                }
            }
        }
    }
    return ans;
}