#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) {
vvl DP(n+1, vl(2, 0));
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;
DP[i][0] = max(DP[i-1][0], DP[i-1][1]);
DP[i][1] = max(
DP[i-1][0] + wp + ws,
DP[i-1][1] - wm + ws
);
}
return max(DP[n][0], DP[n][1]);
}
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;
return sub3(n, m, x, y, w, fish);
}
