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

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

set<int> s[maxn];
map<int, ll> dp[maxn], dpt[maxn], d[maxn];
map<int, ll> pref[maxn], mx[maxn], suff[maxn];
map<int, ll>  a[maxn], mval[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 d=-1;d<=1;d++){
            s[x[i] + d].insert(y[i]);
        }
    }
    s[0].insert(0);
    s[0].insert(n);
    for(int i=1;i<=n;i++){
        s[i].insert(0);
        s[i].insert(n);
        int sum = 0;
        for(int x:s[i]){
            sum += a[i][x];
            pref[i][x] = sum;
        }
    }
    for(int i=1;i<=n;i++){

        ll val = -1e18;

        for(int x:s[i]){
            auto it = s[i-1].upper_bound(x);
            it--;
            int y = *it;
            dp[i][x] = max(mx[i-1][y] + pref[i-1][y], mval[i-1][y]);
            d[i][x] = max(dp[i][x], suff[i-1][x] - pref[i][x]);
            dpt[i][x] = d[i-1][x] + pref[i][x];
            val = max(val, d[i][x]);
            mval[i][x] = val;
            ans = max(ans, d[i][x]);
        }

        val = -1e18;

        for(int x:s[i]){
            val = max(val, max(dp[i][x], dpt[i][x]) - pref[i][x]);
            mx[i][x] = val;
        }

        val = -1e18;

        if(i < n){
            for(auto it = --s[i].end();;it--){
                int x = *it;
                auto I = s[i+1].upper_bound(x);
                I--;
                int y = *I;

                val = max(val, d[i][x] + pref[i+1][y]);
                suff[i][x] = val;
                if(it == s[i].begin()) break;
            }
        }
    }
    return ans;
}