SPyofgame là một chú ếch sống trong một đầm lầy. Trong đầm lầy, có N lá sen được đánh số từ 1 đến N. Các lá sen có tọa độ nguyên trên mặt phẳng tọa độ. SPyofgame chỉ có thể nhảy từ lá sen này qua lá sen khác khi xảy ra 1 trong 2 trường hợp sau:

• \(x_{2}\) > \(x_{1}\) và \(y_{2}\) = \(y_{1}\)
• \(x_{2}\) = \(x_{1}\) và \(y_{2}\) > \(y_{1}\)

Trên mỗi chiếc lá có một số con ruồi và SPyofgame có thể dùng lưỡi của mình để ăn chúng.
SPyofgame hấp thụ một đơn vị năng lượng cho mỗi con ruồi ăn được và sử dụng K đơn vị năng lượng cho mỗi lần nhảy. SPyofgame không thể nhảy nếu không có đủ đơn vị năng lượng trước đó.

SPyofgame muốn đi từ chiếc lá 1 đến chiếc lá N và có lượng năng lượng lớn nhất có thể sau khi đến. SPyofgame ban đầu không có năng lượng và phải thu thập năng lượng cho lần nhảy đầu tiên của mình từ những con ruồi xung quanh chiếc lá 1.

Hãy giúp SPyofgame có thể đi từ 1 đến N với năng lượng lớn nhất.

Input

• Dòng một là hay số nguyên dương N, K ( 2 ≤ N ≤ 300000, 1 ≤ K ≤ 1000)
• i dòng tiếp theo (1 ≤ i ≤ N), mỗi dòng là 3 số nguyên dương X, Y, Z (0 ≤ X, Y ≤ 100000, 0 ≤ Z ≤ 1000) với X, Y là tọa độ lá thứ i, Z là số lượng con ruồi trên chiếc lá mà SPyofgame có thể ăn để tích năng lượng. Lưu ý rằng sẽ không có hai chiếc lá nào cùng tọa độ.

Output

• Dòng đầu tiên in ra số năng lượng của SPyofgame khi đến chiếc lá N.
• Dòng thứ hai in ra M là số lá cây SPyofgame đi qua.

Example

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

5
4