Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Bep là một con ếch không bình thường. Nó sống ở một cái ao có N lá sen nổi trên mặt nước. Các lá sen được đánh dấu từ 1 tới N. Các lá sen được đánh dấu tọa độ theo hệ trục tọa độ Oxy. Điều không bình thường ở con ếch Bep là nó không thể nhảy chéo hay nhảy ngược lại, nó chỉ có thể nhảy tiến lên theo các đoạn thẳng song song với trục tọa độ. Nghĩa là con Bep chỉ có thể nhảy từ lá sen có tọa độ (x1,y1) tới lá sen có tọa độ (x2,y2) nếu:

* y2 = y1 và x2 > x1, hoặc

* x2 = x1 và y2 > y1.

Khi ở trên mỗi lá sen, Bep sẽ dùng lưỡi của mình để bắt ăn tất cả các côn trùng đang ở trên chiếc lá sen ấy.

Con Bep sẽ hấp thụ được một đơn vị năng lượng cho mỗi con côn trùng mà nó ăn được, và sử dụng K đơn vị năng lượng cho mỗi bước nhảy. Nó sẽ không thể thực hiện được bước nhảy nếu như không có đủ năng lượng.

Con ếch Bep muốn nhảy từ lá sen 1 tới lá sen N và có năng lượng lớn nhất có thể sau khi thực hiện bước nhảy cuối cùng. Ban đầu nó không có năng lượng và phải thu thập năng lượng bằng cách ăn hết số côn trùng trên lá sen số 1.

Hãy tìm cách nhảy cho con ếch Bep để nó đạt được năng lượng lớn nhất.

Input

Dòng đầu tiên chứa hai số nguyên N và K (2 ≤ N ≤ 300 000, 1 ≤ K ≤ 1000).

N dòng tiếp theo, dòng thứ i chứa 3 số nguyên X, Y, F (0 ≤ X, Y ≤ 100 000, 0 ≤ F ≤ 1000), biểu diễn lá sen thứ i có tọa độ (X,Y) và có chứa F con côn trùng. Sẽ không có hai lá sen nào trùng tọa độ.

Input luôn được đảm bảo để có đáp số.

Output

Một dòng duy nhất là năng lượng lớn nhất con ếch thu được.

Example

Test 1:

Input:

6 5
1 1 5
2 1 5
1 2 4
2 3 5
3 2 30
3 3 5

Output:

5

Test 2:

Input:

8 10
1 1 15
2 2 30
1 2 8
2 1 7
3 2 8
2 3 7
4 2 100
3 3 15

Output:

36

Test 3:

Input:

9 5
5 5 10
6 5 2
7 5 1
5 6 2
6 6 6
7 6 2
5 7 1
6 7 2
7 7 1

Output:

2