#include "fish.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 310;
ll dp[N][N][N];
ll mat[N][N];
ll pref[N][N];
vector <int> variacoes[N];
ll query(int a, int b, int c, int d){
return pref[c][d] - pref[a-1][d]-pref[c][b-1]+pref[a-1][b-1];
}
ll calc(int i, int y1, int y2, int y3){
if(y2+1 > max(y1, y3)) return 0;
ll sum = query(i, y2+1, i, max(y1, y3));
return sum;
}
ll solve(int i, int y2, int y3){
if(i == 0){
if(y2 == 0) return dp[i][y2][y3] = 0;
return dp[i][y2][y3] = -1e18;
}
if(dp[i][y2][y3] != -1) return dp[i][y2][y3];
dp[i][y2][y3] = -1e18;
for(auto y1 : variacoes[i-1]){
dp[i][y2][y3] = max(dp[i][y2][y3], solve(i-1, y1, y2) +calc(i, y1, y2, y3));
}
return dp[i][y2][y3];
}
long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
memset(dp, -1, sizeof dp);
for(int i = 0;i < m;i++){
mat[X[i]+1][Y[i]+1] = W[i];
variacoes[X[i]+1].push_back(Y[i]+1);
variacoes[X[i]+2].push_back(Y[i]+1);
variacoes[X[i]].push_back(Y[i]+1);
}
for(int i = 1;i < N;i++){
for(int j = 1;j < N;j++){
pref[i][j] = pref[i][j-1]+pref[i-1][j]-pref[i-1][j-1]+mat[i][j];
}
}
variacoes[0].clear();
for(int i = 0;i < N;i++){
variacoes[i].push_back(0);
}
ll ans = 0;
for(int y2 = 0;y2 < N;y2++){
ans = max(ans, solve(n, y2, 0));
}
return ans;
}
