#include "fish.h"
#include <iostream>
#include <vector>
#include <tuple>
#include <set>
#include <algorithm>
#include <map>
using namespace std;
#define ff first
#define ss second
#define ll long long
template<typename T,typename S>
T max(T a,S b){return a>b?a:b;}
int n,m;
vector<int>x,y,w;
ll ans=0;
ll sub2(){
ll cur=0;
if(n==2){
for(int i=0;i<m;i++){
if(x[i]) cur+=w[i];
else ans+=w[i];
}
return max(ans,cur);
}
vector<pair<int,int>>a,b;
for(int i=0;i<m;i++){
if(x[i]&1) cur+=w[i],a.push_back({y[i],w[i]});
else b.push_back({y[i],w[i]});
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
ans=cur;
int j=0;
for(auto [g,f]:b){
cur+=f;
while(j<a.size() && a[j].ff<=g) cur-=a[j].ss,j++;
ans=max(ans,cur);
}
return ans;
}
ll sub3(){
vector<pair<int,int>>a;
for(int i=0;i<m;i++) a.push_back({x[i],w[i]});
a.push_back({n,0});
sort(a.begin(),a.end());
int last=-1;
vector<int>b={0};
for(int i=0;i<=m;i++){
if(a[i].ff-last==1) b.push_back(a[i].ss);
else{
ll cur=0;
vector<ll>pref(b.size()+1),suff(b.size()+2);
pref[0]=0;
suff[b.size()+1]=0;
for(int i=1;i<=b.size();i++){
pref[i]=pref[i-1];
if(i>2){
pref[i]=max({pref[i],pref[i-3]+b[i-1]+b[i-3],pref[i-2]+b[i-1]});
}
else{
pref[i]=max(pref[i],b[i-1]);
}
}
for(int i=b.size();i>0;i--){
suff[i]=suff[i+1];
if(b.size()-i>1){
suff[i]=max({suff[i],suff[i+3]+b[i-1]+b[i+1],suff[i+2]+b[i-1]});
}
else{
suff[i]=max(suff[i],b[i-1]);
}
}
for(int i=0;i<=b.size();i++) cur=max(cur,pref[i]+suff[i+1]);
ans+=cur;
vector<int>ne;
swap(ne,b);
b.push_back(a[i].ss);
}
last=a[i].ff;
}
ll cur=0;
vector<ll>pref(b.size()+1),suff(b.size()+2);
pref[0]=0;
suff[b.size()+1]=0;
for(int i=1;i<=b.size();i++){
pref[i]=pref[i-1];
if(i>2){
pref[i]=max({pref[i],pref[i-3]+b[i-1]+b[i-3],pref[i-2]+b[i-1]});
}
else{
pref[i]=max(pref[i],b[i-1]);
}
}
for(int i=b.size();i>0;i--){
suff[i]=suff[i+1];
if(b.size()-i>1){
suff[i]=max({suff[i],suff[i+3]+b[i-1]+b[i+1],suff[i+2]+b[i-1]});
}
else{
suff[i]=max(suff[i],b[i-1]);
}
}
for(int i=0;i<=b.size();i++) cur=max(cur,pref[i]+suff[i+1]);
ans+=cur;
return ans;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
tie(n,m,x,y,w)=tie(N,M,X,Y,W);
bool su1=true,su2=true,su3=true;
for(int i=0;i<m;i++){
if(x[i]%2==1) su1=false;
if(x[i]>1) su2=false;
if(y[i]!=0) su3=false;
}
if(su1){for(int i=0;i<m;i++) ans+=w[i];return ans;}
if(su2) return sub2();
if(su3) return sub3();
return ans;
}
