题目描述

花火大会开始了！小码姐和小码妹约好一起去看烟花。

两位魔法少女决定要在市里的主街看烟花，主街长为$n$，且恰有$n$个点供市民观赏烟花，相邻点之间距离均恰为$1$。

大会准备了$m$个烟花要放，其中第$i$个烟花放的时间为$t_i$，位置为$p_i$，大小为$a_i$。如果此时站在位置$x$看烟花，则会获得$a_i-|p_i-x|$的快乐度。显然，如果距离太远，小码姐和小码妹会觉得看不真切，反而会获得负的快乐度。

两位魔法少女在每个单位时间内都可以移动最多$d$个单位长度，但是走出主街是不被允许的。在花火大会开始时（即$1$时间时），两位魔法少女可以在任意位置上，她们想要获得的快乐度最大，但她们沉浸于准备去花火大会的快乐中，作为魔法少女的好朋友，小码哥被要求帮助她们计算获得的最大快乐值。然而小码哥不善计算，你能帮帮他吗？

输入格式

第一行输入三个整数$n,m,d$。 接下来$m$行，每行输入三个整数$t_i,p_i,a_i$。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

50 3 1
1 49 1
4 26 1
10 6 1

样例输出 #1

-31

说明/提示

有$1\leq n\leq 10^5,1\leq m\leq 300,1\leq d,p_i\leq n,1\leq t_i,a_i\leq 10^9$，且保证$\forall i\in[1,m),t_i\leq t_{i+1}$。