#include "fish.h"
#include <cstdio>
#include <vector> 
#include <algorithm>
#include <cstring>

#define X first
#define Y second
#define PB push_back
#define debug(...) //fprintf(stderr, __VA_ARGS__)

using namespace std; 

typedef long long ll;
typedef pair<int, int> pii;

const int N = 310;
const ll OO = 1e18;

int n, m, xc[N], yc[N];
ll weg[N], prf[N][N], dp[N][N];

ll max_weights(int nn, int mm, vector<int> X, vector<int> Y, vector<int> W) {
	n = nn;
	m = mm;

	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < N; ++j) { 
			dp[i][j] = -OO;
		}
	}

	for(int i = 0; i < m; ++i) { 
		xc[i] = X[i] + 1;
		yc[i] = Y[i] + 1;
		weg[i] = W[i];
		prf[xc[i]][yc[i]] = weg[i];
	}
	
	for(int i = 0; i <= n; ++i) { 
		for(int j = 1; j <= n; ++j) { 
			prf[i][j] += prf[i][j - 1];
		}
	}

	dp[n + 1][0] = 0;
	for(int i = n; i >= 0; --i) { 
		for(int j = 0; j <= n; ++j) { 
			ll &d = dp[i][j];
			d = 0;
			for(int k = 0; k <= n; ++k) { 
				d = max(d, dp[i + 1][k] + (k < j ? prf[i + 1][j] - prf[i + 1][k] : 0));
			}

			for(int k = 0; k <= n; ++k) { 
				d = max(d, dp[i + 2][k] + prf[i + 1][max(j, k)]);
			}

			for(int k = 0; k <= n; ++k) { 
				d = max(d, dp[i + 3][k] + prf[i + 1][j] + prf[i + 2][k]);
			}
			debug("%d %d %lld\n", i, j, dp[i][j]);
		}
	}
	return dp[0][0];
}