Năm 2025 đánh dấu 50 năm ngày giải phóng miền Nam, thống nhất đất nước (30/4/1975 - 30/4/2025). Để kỷ niệm sự kiện lịch sử trọng đại này, Thành phố Hồ Chí Minh sẽ tổ chức một buổi diễn binh hoành tráng, nhằm tôn vinh những đóng góp của các thế hệ cha anh và khẳng định ý chí, sức mạnh của nhân dân Việt Nam.

Sự kiện không chỉ là dịp để ôn lại lịch sử hào hùng của dân tộc mà còn là cơ hội để thế hệ trẻ hiểu rõ hơn về những giá trị của hòa bình, độc lập và tự do. Đây cũng là dịp để khẳng định quyết tâm xây dựng và phát triển Thành phố Hồ Chí Minh nói riêng và đất nước nói chung.

Sự kiện được diễn ra ở ~n~ quận của Thành phố Hồ Chí Minh. Các quận được đánh số từ ~1~ đến ~n~. Khoảng cách giữa cách quận là 1km

Cuộc diễu hành trên gồm có ~m~ binh chủng sẽ tham gia diễu hành tại các quận. Binh chủng thứ ~i~ sẽ tham gia diễu hành tại quận ~a_i~ vào lúc ~t_i~. Nếu bạn đang ở quận ~x~ vào thời gian ~t_i~ thì niềm vui bạn sẽ nhận được là ~b_i - |a_i - x|~.

Bạn có thể di chuyển ~d~ km mỗi một đơn vị thời gian nhưng bạn không được đi ra khỏi Thành phố Hồ Chí Minh. Ban đầu (thời điểm 1) bạn có thể ở bất kỳ quận nào tại Thành phố Hồ Chí Minh và bạn muốn nhận được niềm vui lớn nhất từ việc xem diễu binh tại Thành phố Hồ Chí Minh. Hãy làm điều đó.

Lưu ý : một hoặc nhiều cuộc diễu binh có thể tiến hành cùng lúc.

Input

Dòng đầu chứ 3 số nguyên dương ~n,m,d~ ~(1 \le n \le 150000,1 \le m \le 300,1 \le d \le n)~.

~m~ dòng tiếp theo, mỗi dòng chứ 3 số ~a_i,b_i,t_i~ ~(1 \le a_i \le n,1 \le b_i \le 10^9,1 \le t_i \le 10^9)~

Ban tổ chức luôn đảm bảo : ~t_i \le t_{i + 1}~

Output

Dòng 1 chứa niềm vui lớn nhất có thể nhận được khi xem diễu binh.

Sample Input 1

10 2 1
1 1000 4
9 1000 4

Sample Output 1

1992

Sample Input 2

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

Sample Output 2

-31