#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
auto n = N, m = M;
auto x = X, y = Y, w = W;
if (n == 1)
return 0;
vector<int> ord(m);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int l, int r)
{ return x[l] < x[r]; });
vector<int> cc;
for (int i = 0; i <= 10; i++)
{
if (x[ord[0]] == i)
break;
cc.push_back(i);
}
for (int i = n - 1; i >= n - 11; i--)
{
if (x[ord[m - 1]] == i)
break;
cc.push_back(i);
}
for (int i = 0; i < m; i++)
cc.push_back(x[ord[i]]);
for (int i = 1; i < m; i++)
if (x[ord[i]] - x[ord[i - 1]] != 1)
{
for (int j = 1; j <= min(10, x[ord[i]] - x[ord[i - 1]] - 1); j++)
cc.push_back(x[ord[i - 1]] + j);
}
sort(cc.begin(), cc.end());
cc.erase(unique(cc.begin(), cc.end()), cc.end());
for (auto &i : x)
i = lower_bound(cc.begin(), cc.end(), i) - cc.begin();
int k = cc.size();
vector<int> v(k);
for (int i = 0; i < m; i++)
v[x[ord[i]]] = w[ord[i]];
vector dp(k, vector<ll>(2, -1));
auto rec = [&](auto self, int i, int j) -> ll
{
if (i == k)
return 0;
auto &ret = dp[i][j];
if (~ret)
return ret;
ret = self(self, i + 1, 0) + (j == 1 ? v[i] : 0);
ret = max(ret, self(self, i + 1, 1));
if (i + 1 < k)
ret = max(ret, self(self, i + 2, 1) + v[i]);
return ret;
};
return rec(rec, 0, 0);
}
