#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const long long oo = 1LL << 60;
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
if (n > 3000)
return 0;
for (int i = 0; i < m; i++)
for (int j = i + 1; j < m; j++)
if (make_pair(x[i], y[i]) > make_pair(x[j], y[j]))
{
swap(x[i], x[j]);
swap(y[i], y[j]);
swap(w[i], w[j]);
}
// f: left, g: right
vector<long long> f(m, -oo), g(m, -oo);
long long ans = 0;
for (int i = 0; i < m;)
{
int ii = i + 1;
while (ii < m && x[ii] == x[i])
ii++;
for (int j = i; j < ii; j++)
if (x[j] < n - 1)
{
g[j] = w[j];
for (int jj = 0; jj < i; jj++)
if (x[jj] == x[j] - 1 && y[jj] >= y[j]) g[j] = max(g[j], f[jj] + w[j]);
else g[j] = max(g[j], max(f[jj], g[jj]) + w[j]);
if (j > i)
g[j] = max(g[j], g[j - 1] + w[j]);
}
for (int j = ii - 1; j >= i; j--)
if (x[j])
{
f[j] = w[j];
for (int jj = 0; jj < i; jj++)
if (x[jj] + 1 < x[j]) f[j] = max(f[j], max(f[jj], g[jj]) + w[j]);
else if (y[jj] > y[j]) f[j] = max(f[j], f[jj] + w[j]);
if (j + 1 < ii)
f[j] = max(f[j], f[j + 1] + w[j]);
}
ans = max({ans, f[i], g[i]});
i = ii;
}
return ans;
}
