Có một con ếch sống trong một cái ao có ~N~ thực vật nổi trên mặt nước. Các thực vật được đánh số từ 1 đến ~N~. Khi xem từ trên cao, vị trí của từng thực vật được đưa ra bởi một cặp tọa độ. Điều đặc biệt là con ếch sợ nhảy theo đường chéo và theo hướng âm. Chính xác hơn, nó có thể nhảy từ một thực vật ở tọa độ ~(x_1, y_1)~ đến thực vật khác có tọa độ ~(x_2, y_2)~ nếu:

• ~x_2 > x_1~ và ~y_2 = y_1~, hoặc
• ~y_2 > y_1~ và ~x_2 = x_1~

Đối với mỗi thực vật, chúng ta biết số lượng ruồi trong vùng lân cận của nó. Con ếch có thể sử dụng lưỡi nhanh chóng ăn tất cả ruồi gần thực vật nó đang ở. Con ếch hấp thụ một đơn vị năng lượng cho mỗi con ruồi nó ăn, và sử dụng ~K~ đơn vị năng lượng cho mỗi bước nhảy. Con ếch không thể thực hiện một bước nhảy nếu nó không có đủ đơn vị năng lượng trước.

Con ếch muốn đi từ thực vật 1 đến thực vật ~N~ để có số năng lượng lớn nhất sau khi đến. Ban đầu ếch không có năng lượng và phải thu thập năng lượng cho bước nhảy đầu tiên của nó từ những con ruồi xung quanh thực vật 1.

Yêu cầu: Tìm chuỗi các thực vật ếch nên đi đến để đạt được mục tiêu của mình.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ (~2 \le N \le 300000, 1 \le K \le 1000~) cách nhau bởi một dấu cách.
• Mỗi dòng trong số ~N~ dòng tiếp theo chứa ba số nguyên ~X, Y~ và ~F~ (~0 \le X, Y \le 100000, 0 \le F \le 1000~) cách nhau bằng dấu cách, có nghĩa là có một thực vật ở tọa độ ~(X, Y)~ với ~F~ con ruồi bay quanh nó.
• Thực vật đầu tiên ở đầu vào là thực vật 1, thứ hai là thực vật 2, ... Không có hai thực vật cùng cặp tọa độ.

Output

• Đưa ra mức năng lượng cuối cùng trên dòng đầu tiên.
• Dòng thứ hai là một số nguyên ~L~, số lượng các thực vật ếch nên đi đến, bao gồm các thực vật từ 1 đến ~N~.
• ~L~ dòng tiếp theo, chuỗi các thực vật ếch đi đến.

Sample Input 1

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

Sample Output 1

5
4
1 1
2 1
2 3
3 3