A festival will be held in a town's main street. There are *n* sections in the main street. The sections are numbered 1 through *n* from left to right. The distance between each adjacent sections is 1.

In the festival *m* fireworks will be launched. The *i*-th (1 ≤ *i* ≤ *m*) launching is on time *t*<sub class="lower-index">*i*</sub> at section *a*<sub class="lower-index">*i*</sub>. If you are at section *x* (1 ≤ *x* ≤ *n*) at the time of *i*-th launching, you'll gain happiness value *b*<sub class="lower-index">*i*</sub> - |*a*<sub class="lower-index">*i*</sub> - *x*| (note that the happiness value might be a negative value).

You can move up to *d* length units in a unit time interval, but it's prohibited to go out of the main street. Also you can be in an arbitrary section at initial time moment (time equals to 1), and want to maximize the sum of happiness that can be gained from watching fireworks. Find the maximum total happiness.

Note that two or more fireworks can be launched at the same time.
The first line contains three integers *n*, *m*, *d* (1 ≤ *n* ≤ 150000; 1 ≤ *m* ≤ 300; 1 ≤ *d* ≤ *n*).

Each of the next *m* lines contains integers *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub>, *t*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ *n*; 1 ≤ *b*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>; 1 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>). The *i*-th line contains description of the *i*-th launching.

It is guaranteed that the condition *t*<sub class="lower-index">*i*</sub> ≤ *t*<sub class="lower-index">*i* + 1</sub> (1 ≤ *i* &lt; *m*) will be satisfied.
import os, sys
import profile
import cProfile
import random
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
from functools import reduce
from io import IOBase, BytesIO
from itertools import count
from operator import xor, add
from typing import List

# region fastio
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# print = lambda d: sys.stdout.write(str(d)+"\n")
def read_int_list(): return list(map(int, input().split()))
def read_int_tuple(): return tuple(map(int, input().split()))
def read_int(): return int(input())

# endregion

### CODE HERE

# f = open('inputs', 'r')
# def input(): return f.readline().rstrip("\r\n")

def MonotonousQueue(nums: List[int], k: int) -> List[int]:
    n, q = len(nums), deque()
    res = [0] * n
    for i in range(min(k, n)):
        while q and nums[i] >= nums[q[-1]]:
            q.pop()
        q.append(i)
        res[i] = nums[q[0]]
    for i in range(k, n):
        while q and nums[i] >= nums[q[-1]]:
            q.pop()
        q.append(i)
        while q[0] <= i - k:
            q.popleft()
        res[i] = nums[q[0]]
    return res

def solve(n, m, d, fireworks):
    dp, cur = [0] * n, 1
    for a, b, t in fireworks:
        a -= 1
        path = d * (t - cur)
        mx = MonotonousQueue(dp, path * 2 + 1)
        for i in range(n):
            dp[i] = mx[min(n - 1, i + path)] + b - abs(a - i)
        cur = t
    return max(dp)

def main():
    for _ in range(1):
        n, m, d = read_int_tuple()
        fireworks = [read_int_tuple() for _ in range(m)]
        print(solve(n, m, d, fireworks))

if __name__ == "__main__":
    main()
    # cProfile.run("main()")
    # profile.run("main()")
