Xem Pháo Hoa

Một lễ hội được tổ chức trên con phố chính của thị trấn. Con phố được chia thành $n$ đoạn, đánh số từ $1$ đến $n$ theo thứ tự từ trái sang phải. Khoảng cách giữa hai đoạn kề nhau bằng $1$.

Trong lễ hội sẽ có $m$ lần bắn pháo hoa. Lần bắn thứ $i$ diễn ra tại thời điểm $t_i$ ở đoạn $a_i$. Nếu tại thời điểm lần bắn thứ $i$ bạn đang đứng ở đoạn $x$ (với $1\le x\le n$), bạn nhận được lượng niềm vui bằng $b_i-|a_i-x|$ (giá trị này có thể âm).

Trong mỗi đơn vị thời gian bạn có thể di chuyển tối đa $d$ đơn vị độ dài, nhưng không được ra khỏi phạm vi con phố (luôn phải ở một đoạn từ $1$ đến $n$). Tại thời điểm ban đầu (thời điểm bằng $1$) bạn được đứng ở một đoạn bất kỳ tùy chọn. Hãy tìm tổng lượng niềm vui lớn nhất có thể thu được sau khi xem toàn bộ các lần bắn pháo hoa.

Lưu ý rằng có thể có hai hay nhiều lần bắn pháo hoa diễn ra cùng một thời điểm. Dữ liệu bảo đảm $t_i\le t_{i+1}$ với mọi $1\le i<m$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $d$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $a_i$, $b_i$, $t_i$ mô tả lần bắn thứ $i$.

Dữ liệu ra

• In ra một số nguyên duy nhất: tổng lượng niềm vui lớn nhất có thể thu được.

Ràng buộc

• $1\le n\le 150000$
• $1\le m\le 300$
• $1\le d\le n$
• $1\le a_i\le n$
• $1\le b_i\le {10}^9$
• $1\le t_i\le {10}^9$
• $t_i\le t_{i+1}$ với mọi $1\le i<m$.

Ví dụ