#include "fish.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;

#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
#define ff fi.fi
#define ss se.se
#define fs fi.se
#define sf se.fi
#define all(x) x.begin(), x.end()
#define endl "\n"

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const int MX=3e5+5;
ll ans[305][305][305][3];
ll n;
ll val[305][305];
ll pref[305][305];
//nw 0 menaik 1 menurun
//awal 0 artinya pertama
//awal 1 artinya diambil depannya
ll dp(int idx, int st, int nw,int awal){
	if(idx>=n || st>n || st<0)return 0;
	if(ans[idx][st][nw][awal]!=-1)return ans[idx][st][nw][awal];
	ll tmp=0;
	ll tambah=0;
	tmp=max(tmp, dp(idx+2, 0,0,1)+pref[idx+1][st]);
	if(nw==0){
		// lagi fase menaik
		//tambahin satu blok
		tambah=0;
		if(awal==1)tambah=val[idx-1][st+1];
		tmp=max(tmp,dp(idx, st+1,nw,awal)+tambah);
		//pindah kolom
		tmp=max(tmp, dp(idx+1, st, nw,1));
		//pindah kolom dan arah
		tmp=max(tmp, dp(idx+1, st,1,1));
	}
	else{
		//lagi fase menurun
		//turunin 1 blok
		tmp=max(tmp,dp(idx, st-1,nw,1)+val[idx][st]);
		//pindah kolom 
		tmp=max(tmp, dp(idx+1, st,nw,1));
	}	
	tmp=max(tmp, dp(idx+2, st,0,1)+pref[idx+1][st]);
	//kalo nextnya lebih pendek
	tmp=max(tmp, dp(idx+2, 0,0,0)+pref[idx+1][st]);
//	cerr<<"ans ["<<idx<<"]["<<st<<"]["<<nw<<"]["<<awal<<"] = "<<tmp<<endl;
	ans[idx][st][nw][awal]=tmp;
	return ans[idx][st][nw][awal];
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    memset(ans,-1, sizeof(ans));
    n=N;
    if(N>300)return 0;
    for(int i=0;i<M;i++){
    	val[X[i]+1][Y[i]+1]=W[i];
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			pref[i][j]=pref[i][j-1]+val[i][j];
		}
	}
	return dp(1,0,0,0);
}

//vector<int> arr1,arr2,arr3;
//int main(){
//	arr1.pb(1);
//	arr1.pb(3);
//	arr2.pb(10);
//	arr2.pb(2);
//	arr3.pb(6);
//	arr3.pb(7);
//	cout<<max_weights(11, 2,arr1,arr2,arr3)<<endl;	
////	for(int i=0;i<15;i++){
////		for(int j=0;j<=15;j++){
////			cerr<<"pref "<<i<<" "<<j<<" = "<<pref[i][j]<<endl;
////		}
////	}
//	return 0;
//}