#include "fish.h"
#include<bits/stdc++.h>
#define pb push_back
#define pf push_front
//#define mp make_pair
#define F first
#define S second
#define ff first
#define ss second
#define str string
#define ll long long
#define ull unsigned ll
#define ld long double
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define pllll pair<pll,pll>
#define pld pair<ld,ld>
#define vl vector<ll>
#define vll vector<pll>
#define vlll vector<plll>
#define vllll vector<pllll>
#define vb vector<bool>
#define sz size()
#define fr front()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bk back();
//#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
using namespace std;
const ld pi=acos(-1.0);
const ll e5=1e5;
const ll e6=1e6;
const ll e9=1e9;
const ll inf=1e18;
const ll mod=1e9+7;
const ll mod2=998244353;
const ll MOD=106710087877475399;
const ll N=3e2+10;
ll bpm(ll x,ll y,ll m){if(y==0)return 1%m;if(y==1)return x%m;ll p=bpm(x,y/2,m);
if(y%2==0)return p*p%m;else return p*p%m*x%m;}
ll bp(ll x,ll y){if(y==0)return 1;if(y==1)return x;ll p=bp(x,y/2);
if(y%2==0)return p*p;else return p*p*x;}
ll s[N][N],dp[N][N][N],pr[N][N],m1[N][N][9],m2[N][N][9];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W){
    for(ll i=0;i<M;i++){
        s[X[i]][Y[i]+1]+=W[i];
    }
    for(ll i=0;i<N;i++){
        pr[i][0]=0;
        for(ll j=1;j<=N;j++) pr[i][j]=pr[i][j-1]+s[i][j];
    }
    for(ll i=0;i<=N;i++){
        for(ll j=0;j<=N;j++){
            if(i==0) dp[0][i][j]=pr[1][i];
            else dp[0][i][j]=-inf;
        }
    }
    ll ans=0;
    for(ll p=1;p<N;p++){
        for(ll b=0;b<9;b++){
            for(ll i=0;i+(1<<b)-1<=N;i++){
                for(ll j=0;j<=N;j++){
                    if(b==0) m1[i][j][b]=dp[p-1][i][j], m2[i][j][b]=dp[p-1][i][j]-pr[p-1][i];
                    else{
                        m1[i][j][b]=max(m1[i][j][b-1],m1[i+(1<<(b-1))][j][b-1]);
                        m2[i][j][b]=max(m2[i][j][b-1],m2[i+(1<<(b-1))][j][b-1]);
                    }
                }
            }
        }
        for(ll j=0;j<=N;j++){
            for(ll k=0;k<=N;k++){
                ll x=pr[p-1][k]-pr[p][min(j,k)]+pr[p+1][k];
                ll y=-inf,lg=31-__builtin_clz(j+1);
                y=max(y, max(m1[0][j][lg],m1[j-(1<<lg)+1][j][lg]) - pr[p-1][min(j,k)]);
                if(j<=k){
                    lg=31-__builtin_clz(k-j+1);
                    y=max(y, max(m2[j][j][lg],m2[k-(1<<lg)+1][j][lg]));
                }
                lg=31-__builtin_clz(N-max(j,k)+1);
                y=max(y, max(m1[max(j,k)][j][lg],m1[N-(1<<lg)+1][j][lg]) - pr[p-1][k]);
                dp[p][j][k]=x+y;
                
                if(p==N-1) ans=max(ans,dp[p][j][k]);
            }
        }
    }
    return ans;
}
// dp[p][j][k]=max: dp[p-1][i][j] + pr[p-1][k]-pr[p-1][min(max(i,j),k)] - pr[p][min(j,k)] + pr[p+1][k]