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 đánh số từ 1 đến N.

Mỗi thực vật có:

• Tọa độ (x, y)
• Số lượng ruồi F

Con ếch bắt đầu tại thực vật 1 và muốn đi đến thực vật N.

Quy tắc di chuyển

Ếch chỉ có thể nhảy từ thực vật (x1, y1) đến (x2, y2) theo quy tắc:

• x2 > x1 và y2 = y1 (nhảy sang phải), hoặc
• y2 > y1 và x2 = x1 (nhảy lên trên)

Năng lượng

• Ban đầu: ếch có 0 năng lượng
• Khi đứng tại một thực vật: ăn hết ruồi → nhận F năng lượng
• Mỗi lần nhảy: mất K năng lượng
• Chỉ được nhảy khi đủ năng lượng

Hãy tìm đường đi từ thực vật 1 → thực vật N sao cho năng lượng cuối cùng của ếch là lớn nhất

Dữ liệu vào (test.inp)

• Dòng 1: hai số nguyên N K
• N dòng tiếp theo, dòng thứ i gồm ba số nguyên Xi Yi Fi
  • Tọa độ (Xi, Yi)
  • Số ruồi Fi

(Không có hai thực vật trùng tọa độ)

Dữ liệu ra (test.out)

• Dòng 1: một số nguyên — năng lượng lớn nhất đạt được khi đến thực vật N
• Dòng 2: một số nguyên L — số lượng thực vật trong đường đi
• L dòng tiếp theo: mỗi dòng ghi tọa độ (x, y) của các thực vật theo thứ tự di chuyển