第一眼看是线段交集问题，感觉不会= =。然后发现n是1000，那好像可以n^2建图再做。一想到这里，突然醒悟，直接记忆化搜索就好了啊。。太蠢了。。
代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = + ; int n,m,r;
struct node
{
int l,r,val;
void read() {scanf("%d%d%d",&l,&r,&val);}
}p[N]; int dp[N];
int dfs(int u)
{
if(dp[u] != -) return dp[u];
int ans = p[u].val;
for(int i=;i<=m;i++)
{
if(p[u].r + r <= p[i].l)
{
ans = max(ans, p[u].val + dfs(i));
}
}
return dp[u] = ans;
} int main()
{
while(scanf("%d%d%d",&n,&m,&r) == )
{
for(int i=;i<=m;i++) p[i].read();
memset(dp,-,sizeof dp);
int ans = ;
for(int i=;i<=m;i++) ans = max(ans, dfs(i));
printf("%d\n",ans);
}
return ;
}