Sau những biến cố xảy đến trong cuộc đời, kéo theo những thiệt hại to lớn về mặt vật chất lẫn tinh thần, cụ thể ở đây là đánh bài xì dách, BD, một nam sinh vui vẻ, hòa đồng, yêu màu Hường, bỗng chốc trở thành một kẻ yêu bánh ngọt, ghiền bánh bèo, nghiện bánh bông lan và cuồng bánh kem. Là người bạn thân nhất của BD, SM không thể cam lòng khi thấy người bạn thân thiết của mình trở nên như vậy, SM liền nghĩ ra những lời khuyên chân thành để gửi đến người bạn cuồng bánh của mình nhằm giúp cậu ấy trở về lại chính mình, nhưng mọi chuyện đâu dễ như vậy, để có thể gửi những lời nhắn đó đến cậu ta thì phải làm cho BD chịu lắng nghe mình trước. Chính vì vậy, SM buộc phải bỏ ra những đồng tiền tiết kiệm từ những ván bài đỏ đen - thứ đã chuôi rèn nên một con người cứng cỏi bây giờ, để mua một chiếc bánh kem màu Hường thật xinh xắn nhằm đưa được những tâm tư mà cậu muốn truyền đạt đến người bạn thân của mình. Khi ở tiệm bánh, cậu lại nhận ra rằng chiếc bánh kem quá to khi có chiều cao là \(k\) còn chiều dài và chiều rộng lên đến vô cực. Cậu cần phải nhờ người bán bánh cắt bánh nhỏ lại sao cho độ ngon miệng đạt được là cao nhất.

- Độ ngon miệng của một cách cắt là tổng thể tích bánh được cắt ra từ chiếc bánh kem trừ tổng chi phí để cắt được những miếng bánh đó.

- Một cách cắt bánh là tập hợp một hay nhiều lát cắt.

- Một lát cắt được biểu diễn dưới dạng một bộ số \((x[i], y[i], c[i])\) là hình hộp chữ nhật có tọa độ trái dưới là \((0, 0, 0)\), phải trên là \((x[i], y[i], k)\) với \(k\) là chiều cao của chiếc bánh và chi phí thực hiện lát cắt là \(c[i]\).

• Nói cách khác: Gọi Độ Ngon Miệng là \(D\). \(Cut_1, Cut_2, ..., Cut_m\) là các lát cắt trong cách cắt được chọn và \(V\) là tổng thể tích bánh được cắt ra. Ta có \(D\) \(=\) $V - $\(\sum\limits_{i = 1}^m\) \(c[Cut_i]\). Và bạn cần tìm cách cắt sao cho \(D\) đạt giá trị *lớn nhất *.

Vì quá lo mải mê nghĩ ra những vần thơ hay, những tâm tư đẹp để gửi đến người thương, SM không thể tập trung suy nghĩ ra cách cắt chiếc bánh đó được, vì vậy các bạn hãy giúp SM cắt chiếc bánh kem màu Hường ngọt ngào ấy nhé$.

Input

• Dòng đầu tiên chứa 2 số nguyên dương \(N\) và \(k\) \((1 \le N \le 5 * 10^5, 1 \le k \le 3)\) là số lát cắt mà SM có thể nhờ người bán bánh cắt và chiều cao của chiếc bánh.
• Mỗi dòng trong \(N\) dòng tiếp theo gồm bộ số nguyên \((x[i], y[i], c[i])\) \((1 \le x[i], y[i], c[i] \le 10^9)\)

Output

• Gồm duy nhất một số nguyên \(D\) là độ ngon miệng lớn nhất có thể đạt được.

Scoring

• Subtask #1 (\(40\%\) số điểm): \(N \le 2000\).
• Subtask #2 (\(60\%\) số điểm): \(N \le 5 * 10^5\).

Example

4 3
1 6 2
6 2 7
2 4 3
5 3 8

44