#include "fish.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 1e18;
long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y,
std::vector<int> w) {
ll sub1 = 1, sub2 = 1, sub3 = 1;
n++;
vector<vector<pair<ll,ll>>> a(n);
vector<vector<ll>> b(n);
for(ll i = 0;i<m;i++){
a[x[i]].push_back({y[i],w[i]});
if(x[i]) b[x[i]-1].push_back(y[i]);
b[x[i]+1].push_back(y[i]);
if(x[i]&1) sub1 = 0;
if(x[i]>1) sub2 = 0;
if(y[i]) sub3 = 0;
}
//cerr << sub1 << " " << sub2 << " " << sub3 << "\n";
n--;
for(auto &o : a) sort(o.begin(),o.end());
for(auto &o : b) sort(o.begin(),o.end());
if (sub1){
ll ans = 0;
for(ll i : w) ans += i;
return ans;
}
if(sub2){
ll a1 = 0, a2 = 0;
vector<array<ll,3>> o;
for(auto [p,v] : a[0]) a1+=v,o.push_back({p,1,v});
for(auto [p,v] : a[1]) a2+=v,o.push_back({p,0,v});
ll ans = max(a1,a2);
if(n>2){
sort(o.begin(),o.end());
ll dp0 = 0, dp1 = 0;
for(auto &u : o){
if (u[1]){
dp0 += u[2];
dp1 = max(dp1,dp0);
}else{
dp1 += u[2];
}
}
ans = max(ans,dp1);
}
return ans;
}
if (sub3){
ll ans = 0;
for(ll i : w) ans += i;
vector<ll> dp(n+1,big);
dp[0] = 0;
for(ll i = 0;i<n;i++){
ll cur = a[i].size()?a[i][0].second:0;
dp[i+1] = min(dp[i+1],dp[i]+cur);
if(i>=1)dp[i+1] = min(dp[i+1],dp[i-1]+cur);
if(i>=3)dp[i+1] = min(dp[i+1],dp[i-2]+cur);
}
//for(ll i = 0;i<=n;i++) cerr << dp[i] << " \n"[i==n];
ll de = min(dp.back(),dp.end()[-2]);
return ans-de;
}
return 0;
}
