Description：

$n$ 个格子排成一排，在 $t_i$ 时刻会有一只分值为 $w_i$ 的鼹鼠出现在位置 $x_i$ 上，有一个锤子，刚开始在任何位置，每一时刻可以移动不超过 $p$ 的距离，如果锤子和鼹鼠在同一时刻出现在同一位置，那么可以获得得分，求最大得分。

$1\leqslant m \leqslant 10^5$

Solution：

如果把时间看成横坐标，位置看成纵坐标，那么一个锤子能打到的范围就是图中蓝色区域，但是这样很不好求，考虑用曼哈顿距离与切比雪夫距离的转化把坐标变成 $(-x-y,-x+y)$ ，那么锤子能打到的范围就是一个点左下角的一部分。于是这就是一个二维偏序问题，可以用排序 $+$ 树状数组。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,m;

#define MAXN 100010

struct point

{

	int t,w,p;

	int x,y;

}p[MAXN];

bool cmp_x(point a,point b){return (a.x == b.x ? a.y < b.y : a.x < b.x);}

bool cmp_y(point a,point b){return a.y < b.y;}

int b[MAXN],tot = 0;

int c[MAXN];

int lowbit(int x){return x & (-x);}

void add(int p,int x){for(int i = p;i <= n;i += lowbit(i))c[i] = max(c[i],x);return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res = max(res,c[i]);return res;}

int main()

{

	read();n = read();m = read();

	int x,y;

	for(int i = 1;i <= n;++i)

	{

		p[i].t = read();p[i].w = read();p[i].p = read();

		x = p[i].t * m;y = p[i].p;

		p[i].x = -x - y;p[i].y = -x + y;

		b[i] = p[i].y;

	}

	sort(p + 1,p + 1 + n,cmp_y);

	sort(b + 1,b + 1 + n);

	for(int i = 1;i <= n;++i)

		if(i == 1 || b[i] != b[i - 1])

			p[i].y = ++tot;

		else p[i].y = tot;

	sort(p + 1,p + 1 + n,cmp_x);

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		int k = query(p[i].y);

		add(p[i].y,k + p[i].w);

	}

	cout << query(tot) << endl;

	return 0;

}