#include "fish.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 310;
const int MAXY = 10;
map <array <int, 3>, ll> dp;
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 valor_dp(int a, int b, int c){
if(a == 0 and b == 0) return dp[{a, b, c}] = 0;
if(dp.find({a, b, c}) != dp.end()) return -1e18;
return dp[{a, b, c}];
}
ll solve(int i, int y2, int y3){
if(i == 0){
if(y2 == 0) return dp[{i, y2, y3}] = 0;
return -1e18;
}
if(dp.find({i, y2, y3}) != dp.end()) 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) {
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 y1 = 0;y1 < MAXY;y1++){
for(int y2 = 0;y2 < MAXY;y2++){
ans = max(ans, solve(n, y2, 0));
}
}
return ans;
}
