#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 1000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
//mt19937 R(time(0));
map < string , int > ma , ma1 ;
#include "fish.h"
ll sum[ 305 ][ 305 ] ;
ll pos[ 305 ][ 305 ] ;
ll dp_bl[ 305 ][ 305 ] ;
ll dp_dk[ 305 ][ 305 ] ;
//vector < pair < int , int > > v[ 305 ] ;
ll ss[ 2 ][ N ] , ps[ 2 ][ N ] ;
ll get1( int N, int M, vector<int> X, vector<int> Y,vector<int> W ){
FOR( i , M ){
ps[ X[ i ] ][ Y[ i ] ] = W[ i ] ;
}
FOR( i , N ){
FOR( j , N ){
if( j != 0 ) ss[ i ][ j ] = ss[ i ][ j - 1 ] ;
ss[ i ][ j ] += ps[ i ][ j ] ;
}
}
if( N == 1 ) return 0LL ;
if( N <= 2 ){
ll ans = 0 ;
FOR( i , N ) ans = max( ans , max( ss[ 0 ][ i ] , ss[ 1 ][ i ] ) ) ;
return ans ;
}
ll ans = 0 ;
FOR( i , N ) ans = max( ans , max( ss[ 0 ][ i ] , ss[ 1 ][ i ] ) ) ;
FOR( i , N + 1 ){
ll cur = 0 ;
cur = ss[ 1 ][ N ] ;
if( i != 0 ) cur = cur - ss[ 1 ][ i - 1 ] ;
if( i != 0 ){
cur = cur + ss[ 0 ][ i - 1 ] ;
}
ans = max( ans , cur ) ;
}
return ans ;
}
ll sum2[ N ][ 4 ] ;
ll pos2[ N ][ 4 ] ;
ll dp_bl2[ N ][ 4 ] ;
ll dp_dk2[ N ][ 4 ] ;
ll get2( int N, int M, vector<int> X, vector<int> Y,vector<int> W ){
FOR( i , M ){
pos2[ X[ i ] ][ Y[ i ] ] = W[ i ] ;
}
int m = min( N , 3 ) ;
FOR( i , N ){
FOR( j , m ){
if( j != 0 ) sum2[ i ][ j ] = sum2[ i ][ j - 1 ] ;
sum2[ i ][ j ] += pos2[ i ][ j ] ;
}
}
// dp_bl
// dp_dk
FOR( i , N ){
if( i == 0 ){
FOR( j , m + 1 ){
dp_bl2[ i ][ j ] = 0 ;
dp_dk2[ i ][ j ] = 0 ;
}
continue ;
}
FOR( j , m + 1 ){
// j ari sadamdec ginda kedeli
// cases
// pirveli ginda ro winas kedeli amaze maxali iyos
for( int wn = j ; wn < m + 1 ; wn ++ ){
ll cur ;
ll sm = 0 ;
if( wn != 0 ) sm = sum2[ i ][ wn - 1 ] ;
if( j != 0 ) sm = sm - sum2[ i ][ j - 1 ] ;
cur = dp_bl2[ i - 1 ][ wn ] + sm ;
dp_bl2[ i ][ j ] = max( dp_bl2[ i ][ j ] , cur ) ;
dp_dk2[ i ][ wn ] = max( dp_dk2[ i ][ wn ] , cur ) ;
}
for( int wn = 0 ; wn <= j ; wn ++ ){
ll cur ;
ll sm = sum2[ i - 1 ][ j - 1 ] ;
if( wn != 0 ) sm = sm - sum2[ i - 1 ][ wn - 1 ] ;
cur = sm + dp_dk2[ i - 1 ][ wn ] ;
dp_bl2[ i ][ j ] = max( dp_bl2[ i ][ j ] , cur ) ;
dp_dk2[ i ][ j ] = max( dp_dk2[ i ][ j ] , cur ) ;
}
}
}
ll ans = 0 ;
FOR( j , m + 1 ){
ans = max( ans , dp_bl2[ N - 1 ][ j ] ) ;
ans = max( ans , dp_dk2[ N - 1 ][ j ] ) ;
}
return ans ;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W){
int tt = 0 ;
ll sm = 0 , mm = 0 , mm1 = 0 ;
FOR( i , M ){
sm = sm + W[ i ] ;
if( X[ i ] % 2 == 1 ) tt =-1 ;
mm = max( mm , X[ i ]*( 1LL) ) ;
mm1 = max( mm1 , Y[ i ]*( 1LL ) ) ;
}
if( tt == 0 ) return sm ;
if( mm <= 1 ){
return get1( N , M , X , Y , W ) ;
}
if( mm1 == 0 ){
return get2( N , M , X , Y , W ) ;
}
FOR( i , M ){
pos[ X[ i ] ][ Y[ i ] ] = W[ i ] ;
}
FOR( i , N ){
FOR( j , N ){
if( j != 0 ) sum[ i ][ j ] = sum[ i ][ j - 1 ] ;
sum[ i ][ j ] += pos[ i ][ j ] ;
}
}
// dp_bl
// dp_dk
FOR( i , N ){
if( i == 0 ){
FOR( j , N + 1 ){
dp_bl[ i ][ j ] = 0 ;
dp_dk[ i ][ j ] = 0 ;
}
continue ;
}
FOR( j , N + 1 ){
// j ari sadamdec ginda kedeli
// cases
// pirveli ginda ro winas kedeli amaze maxali iyos
for( int wn = j ; wn < N + 1 ; wn ++ ){
ll cur ;
ll sm = 0 ;
if( wn != 0 ) sm = sum[ i ][ wn - 1 ] ;
if( j != 0 ) sm = sm - sum[ i ][ j - 1 ] ;
cur = dp_bl[ i - 1 ][ wn ] + sm ;
dp_bl[ i ][ j ] = max( dp_bl[ i ][ j ] , cur ) ;
dp_dk[ i ][ wn ] = max( dp_dk[ i ][ wn ] , cur ) ;
}
for( int wn = 0 ; wn <= j ; wn ++ ){
ll cur ;
ll sm = sum[ i - 1 ][ j - 1 ] ;
if( wn != 0 ) sm = sm - sum[ i - 1 ][ wn - 1 ] ;
cur = sm + dp_dk[ i - 1 ][ wn ] ;
dp_bl[ i ][ j ] = max( dp_bl[ i ][ j ] , cur ) ;
dp_dk[ i ][ j ] = max( dp_dk[ i ][ j ] , cur ) ;
}
}
}
ll ans = 0 ;
FOR( j , N + 1 ){
ans = max( ans , dp_bl[ N - 1 ][ j ] ) ;
ans = max( ans , dp_dk[ N - 1 ][ j ] ) ;
}
return ans ;
}
// int main() {
// int N, M;
// assert(2 == scanf("%d %d", &N, &M));
// std::vector<int> X(M), Y(M), W(M);
// for (int i = 0; i < M; ++i) {
// assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
// }
// long long result = max_weights(N, M, X, Y, W);
// printf("%lld\n", result);
// return 0;
// }
