#include "fish.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define lb lower_bound
#define ub upper_bound
#define mem(a,i) memset(a,i,sizeof(a))
const int MAX=2e5+10;
int n;
vector<pair<ll,ll>> y[MAX];
vector<ll> p[MAX];
vector<vector<ll>> dp[MAX];
vector<ll> can[MAX];
ll getSum(int x,ll l,ll r){
if(l>r)return 0;
int L=lb(all(y[x]),make_pair(l,0ll))-y[x].begin();
int R=ub(all(y[x]),make_pair(r+1,0ll))-y[x].begin()-1;
if(L<=R){
if(L==0)return p[x][R];
return p[x][R]-p[x][L-1];
}
return 0;
}
vector<vector<ll>> sumF[MAX];
vector<vector<ll>> sumB[MAX];
vector<pair<int,int>> vec[MAX];
vector<vector<ll>> w;
struct t300{
ll dp[310][310][2];
ll getP(int i,int l,int r){
if(l>r||i==0)return 0;
return p[i][r]-p[i][l-1];
}
ll solve300(){
for(int i=1;i<=n;i++){
p[i].resize(n+10);
p[i][0]=0;
for(int j=1;j<=n;j++){
p[i][j]=p[i][j-1]+w[i][j];
}
}
mem(dp,0);
for(int i=2;i<=n;i++){
{
ll mx=0;
for(int j=n;j>=1;j--){
mx=max(mx,max(dp[i-1][j][0],dp[i-1][j][1])+p[i][j]);
dp[i][j][0]=mx-p[i][j];
}
}
for(int j=0;j<=n;j++){
{
for(int f=0;f<=j;f++){
dp[i][j][1]=max(dp[i][j][1],dp[i-1][f][1]+getP(i-1,f+1,j));
}
dp[i][j][1]=max(dp[i][j][1],dp[i-1][0][0]);
}
}
}
ll ans=0;
for(int j=0;j<=n;j++)ans=max(ans,max(dp[n][j][0],dp[n][j][1]));
return ans;
}
};
long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W) {
// assert(N<=300);
n=N;
int MX=0;
bool sub=1;
for(int i=0;i<M;i++){
X[i]++;
Y[i]++;
y[X[i]].pb({Y[i],i});
vec[Y[i]].pb({X[i],W[i]});
sub&=(X[i]%2==1);
MX=max(MX,X[i]);
}
if(sub){
ll ans=0;
for(int i=0;i<M;i++)ans+=W[i];
return ans;
}
if(MX<=2){
if(N==2){
ll f=0,f1=0;
for(int i=0;i<M;i++){
if(X[i]%2)f+=W[i];
else f1+=W[i];
}
return max(f,f1);
}
ll sum=0;
for(int i=0;i<M;i++){
if(X[i]%2==0)sum+=W[i];
}
ll ans=sum;
for(int i=1;i<=N;i++){
for(auto [x,w]:vec[i]){
if(x%2==1)sum+=w;
else sum-=w;
}
ans=max(ans,sum);
}
return ans;
}
for(int i=1;i<=N;i++){
if(y[i].empty())continue;
sort(all(y[i]));
p[i].pb(W[y[i][0].S]);
for(int j=1;j<sz(y[i]);j++){
p[i].pb(p[i].back()+W[y[i][j].S]);
}
}
if(N<=300){
w.resize(N+10);
for(int i=1;i<=n;i++){
w[i].resize(n+10);
for(int j=1;j<=n;j++){
w[i][j]=0;
}
for(auto [pos,num]:y[i])w[i][pos]=W[num];
}
t300 FFF;
return FFF.solve300();
}
can[0].pb(0);
can[N+1].pb(0);
for(int i=1;i<=N;i++){
can[i].pb(0);
if(i>0){
for(auto [x,b]:y[i-1])can[i].pb(x);
}
if(i+1<=N){
for(auto [x,b]:y[i+1])can[i].pb(x);
}
sort(all(can[i]));
can[i].erase(unique(all(can[i])),can[i].end());
}
for(int i=1;i<=N+1;i++){
dp[i].resize(sz(can[i]));
for(int j=0;j<sz(dp[i]);j++){
dp[i][j].resize(sz(can[i-1]));
for(int k=0;k<sz(can[i-1]);k++){
dp[i][j][k]=0;
}
}
}
for(int i=0;i<N;i++){
sumF[i].resize(sz(can[i]));
for(int j=0;j<sz(can[i]);j++){
sumF[i][j].resize(sz(can[i+1]));
for(int k=0;k<sz(can[i+1]);k++){
sumF[i][j][k]=getSum(i+1,can[i+1][k]+1,can[i][j]);
}
}
}
for(int i=1;i<=N+1;i++){
sumB[i].resize(sz(can[i]));
for(int j=0;j<sz(can[i]);j++){
sumB[i][j].resize(sz(can[i-1]));
for(int k=0;k<sz(can[i-1]);k++){
sumB[i][j][k]=getSum(i-1,can[i-1][k]+1,can[i][j]);
}
}
}
for(int i=1;i<=N;i++){
for(int j=0;j<sz(can[i]);j++){
for(int k=0;k<sz(can[i-1]);k++){
for(int f=0;f<sz(can[i+1]);f++){
ll nxt=dp[i][j][k];
{
nxt+=max(sumF[i-1][k][j],sumB[i+1][f][j]);
}
dp[i+1][f][j]=max(dp[i+1][f][j],nxt);
}
}
}
}
ll ans=0;
for(int j=0;j<sz(can[N]);j++)ans=max(ans,dp[N+1][0][j]);
return ans;
}
