设(f[i])表示考虑了前(i)个馅饼且第(i)个必接的最大收益，先写出转移方程
[f[i]=max_{j合法}{f[j]}+w_i
]
(j)合法究竟意味着什么？
不难发现，就是 (dis(i,j)leq 速度 imes (t[i]-t[j]))
速度有1有2，很麻烦，所以我们把时间全部乘2，速度就是1了
现在判合法就简单了，可以写出清晰的式子
[mid x[j]-x[i]mid leq t[i]-t[j]
]
解出来
[egin{align*}
t[j]+x[j]&geq t[i]+x[i]\ x[j]-t[j]&leq x[i]-t[i]
end{align*}
]
二者是或的关系，这就是一个二维偏序问题
因此我们按(t[i]+x[i])降序排序，用树状数组查询下标(x[i]-t[i])前缀最小值，即可将方程优化到(O(nlogn))
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
inline int rd(){
int ret=0,f=1;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
while(isdigit(c))ret=ret*10+c-'0',c=getchar();
return ret*f;
}
#define space() putchar(' ')
#define nextline() putchar('
')
void pot(int x){if(!x)return;pot(x/10);putchar('0'+x%10);}
void out(int x){if(!x)putchar('0');if(x<0)putchar('-'),x=-x;pot(x);}
const int MAXN = 100005;
inline void upmax(int &x,int y){x=max(x,y);}
struct Node{
int a,b,w;
Node(int x=0,int y=0,int z=0){a=x;b=y;w=z;}
bool operator<(const Node &rhs)const{
return a>rhs.a;
}
}node[MAXN];
int n,m;
int sav[MAXN];
int bit[MAXN];
int f[MAXN];
void update(int x,int w){
for(int i=x;i<=n;i+=i&-i)upmax(bit[i],w);
}
int query(int x){
int ret=0;
for(int i=x;i;i-=i&-i)upmax(ret,bit[i]);
return ret;
}
signed main(){
m=rd();n=rd();
int t,p,w;
for(int i=1;i<=n;i++){
t=rd();p=rd();w=rd();t<<=1;
node[i]=Node(t+p,p-t,w);
sav[i]=p-t;
}
sort(sav+1,sav+1+n);
int tot=unique(sav+1,sav+1+n)-sav-1;
for(int i=1;i<=n;i++){
node[i].b=lower_bound(sav+1,sav+tot,node[i].b)-sav;
}
sort(node+1,node+1+n);
int ans=0;
for(int i=1;i<=n;i++){
f[i]=query(node[i].b)+node[i].w;
update(node[i].b,f[i]);
upmax(ans,f[i]);
}
out(ans);
return 0;
}