#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=3e5+5;
ll n,m,x[mxn],y[mxn],arr[mxn],val[305][305],pre[305][305],dp[305][305][2];
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
n=N;
m=M;
bool t1=true,t2=true,t3=true;
ll sum=0;
for(int i=0;i<m;i++){
x[i]=X[i];
y[i]=Y[i];
arr[i]=W[i];
sum+=arr[i];
if(x[i]%2) t1=false;
if(x[i]>1) t2=false;
if(y[i]!=0) t3=false;
}
if(t1){
return sum;
}
if(t2){
vector<int>a(n+5),b(n+5);
ll k=0;
for(int i=0;i<m;i++){
if(x[i]==0){
a[y[i]]=arr[i];
}
else{
b[y[i]]=arr[i];
k+=arr[i];
}
}
if(n==2){
return max(a[0]+a[1],b[0]+b[1]);
}
ll ans=k;
for(int i=0;i<n;i++){
k-=b[i];
k+=a[i];
ans=max(ans,k);
}
return ans;
}
if(t3){
vector<vector<ll>>dp(n+5,vector<ll>(3));
vector<ll>val(n+5);
for(int i=0;i<m;i++){
val[x[i]]=arr[i];
}
for(int i=1;i<n;i++){
dp[i][1]=dp[i-1][1];
if(i>1){
dp[i][1]=max(dp[i-1][1],max(dp[i-2][1],dp[i-2][0])+val[i-1]);
}
else{
dp[i][1]=val[i-1];
}
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+val[i]);
}
return max(dp[n-1][1],dp[n-1][0]);
}
for(int i=0;i<m;i++){
val[x[i]+1][y[i]+1]=arr[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
pre[j][i]=pre[j-1][i]+val[i][j];
}
}
ll ans=0;
for(int i=2;i<=n;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<j;k++){
dp[i][j][1]=max(dp[i][j][1],dp[i-1][k][1]+pre[j][i-1]-pre[k][i-1]);
}
for(int k=0;k<=n&&i>1;k++){
if(i==2){
dp[i][j][1]=pre[j][i-1];
dp[i][j][0]=pre[j][i-1];
}
else{
dp[i][j][1]=max(dp[i][j][1],max(dp[i-2][k][1],dp[i-2][k][0])+pre[max(k,j)][i-1]);
dp[i][j][0]=max(dp[i][j][0],max(dp[i-2][k][1],dp[i-2][k][0])+pre[max(k,j)][i-1]);
}
}
for(int k=j;k<=n;k++){
dp[i][j][0]=max(dp[i][j][0],max(dp[i-1][k][0],dp[i-1][k][1])+pre[k][i]-pre[j][i]);
}
}
}
for(int i=0;i<=n;i++){
ans=max(ans,dp[n][i][0]);
ans=max(ans,dp[n][i][1]);
}
return ans;
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
