#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi =vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
ll sub1(int n, int m, vi &x, vi &y, vl &w, map<pair<int, int>, int> &fish) {
return accumulate(w.begin(), w.end(), 0LL);
}
ll sub2(int n, int m, vi &x, vi &y, vl &w, map<pair<int, int>, int> &fish) {
if (n <= 2) {
ll asum = 0, bsum = 0;
for (int i = 0; i < m; i++) {
if (x[i] == 0) asum += w[i];
else bsum += w[i];
}
return max(asum, bsum);
} else {
vl prefa(n+1), prefb(n+1);
for (int i = 1; i <= n; i++) {
prefa[i] = prefa[i-1];
prefb[i] = prefb[i-1];
if (fish.count({0, i-1})) prefa[i] += w[fish[{0, i-1}]];
if (fish.count({1, i-1})) prefb[i] += w[fish[{1, i-1}]];
}
ll ans = prefb[n];
for (int i = 1; i <= n; i++) {
ans = max(ans, prefa[i] + prefb[n] - prefb[i]);
}
return ans;
}
}
ll sub3(int n, int m, vi &x, vi &y, vl &w, map<pair<int, int>, int> &fish) {
vl DP(n+1, 0LL);
for (int i = 1; i <= n; i++) {
ll wp = fish.count({i-2, 0}) ? w[fish[{i-2, 0}]] : 0LL;
ll wm = fish.count({i-1, 0}) ? w[fish[{i-1, 0}]] : 0LL;
ll ws = fish.count({i, 0}) ? w[fish[{i, 0}]] : 0LL;
for (int j = 0; j < i; j++) {
ll pot = DP[j] + wp + ws;
if (j >= i - 1) pot -= wm;
if (j >= i - 2) pot -= wp;
DP[i] = max(DP[i], pot);
}
}
return *max_element(DP.begin(), DP.end());
}
ll max_weights(int n, int m, vi x, vi y, vi W) {
vl w(W.begin(), W.end());
map<pair<int, int>, int> fish; for (int i = 0; i < m; i++) fish[{x[i], y[i]}] = i;
// for (auto &el : fish) {
// cout << el.first.first << " " << el.first.second << " " << el.second << "\n";
// }
return sub3(n, m, x, y, w, fish);
}
