An đang tham gia một trò chơi điện tử bao gồm các màn diệt quái vật. Mỗi quái vật và siêu anh hùng trong trò chơi sẽ có ba đặc tính:

• Lượng máu (kí hiệu là ~h~).
• Sát thương tấn công (kí hiệu là ~a~).
• Phòng thủ (kí hiệu là ~d~).

Như vậy, một nhân vật có lượng máu là ~x~, sát thương tấn công là ~y~, khả năng phòng thủ là ~z~ sẽ được ký hiệu là ~(x,y,z)~. Một siêu anh hùng ~(u, v, w)~ sẽ chiến thắng quái vật ~(x,y,z)~ khi và chỉ khi cả ba điều kiện sau đều thỏa mãn:

• ~u \geq x~.
• ~v \geq y~.
• ~w \geq z~.

Bắt đầu mỗi màn, An sẽ nhận được các thông tin:

• ~n~ là số lượng quái vật có trong màn chơi.
• ~k~ là số quái vật ít nhất An cần phải chiến thắng để qua màn.
• ~n~ bộ ba ~(x,y,z)~ là đặc tính của từng con quái vật.

Trước khi chiến đấu, An cần phải xây dựng một siêu anh hùng ~(u,v,w)~ với chi phí là ~u+v+w~. Để qua màn, siêu anh hùng của An cần phải chiến thắng ít nhất ~k~ quái vật.

Yêu cầu:

Hãy giúp An xây dựng siêu anh hùng với chi phí thấp nhất sao cho An vẫn có thể qua màn.

Input (vào từ GAME.INP):

• Dòng đầu chứa hai số nguyên dương ~n~ và ~k~ (~1 \leq k \leq n \leq 5 \times 10^5~).
• ~n~ dòng tiếp theo, mỗi dòng chứa bộ ba số nguyên ~x,y,z~ cách nhau bởi dấu cách (~1 \leq x,y,z \leq 300~).

Output (xuất ra GAME.OUT):

• Gồm một số nguyên dương là chi phí thấp nhất để An có thể vượt qua màn.

Ví dụ:

Sample Input 1

3 2
1 2 3
4 5 1
3 1 4

Sample Output 1

9

Note

• An sẽ xây dựng siêu anh hùng ~(3, 2, 4)~ với chi phí là ~3+2+4=9~. Siêu anh hùng này sẽ chiến thắng được quái vật ~(1,2,3)~ và ~(3,1,4)~.

Subtask:

• ~10\%~ số test tương ứng với ~10\%~ số điểm có ~k = n~.
• ~30\%~ số test tương ứng với ~30\%~ số điểm có ~x,y,z \leq 100~ và ~n \leq 100~.
• ~30\%~ số test tương ứng với ~30\%~ số điểm có ~z = 1~ với tất cả ~n~ quái vật.
• ~30\%~ số test tương ứng với ~30\%~ số điểm không có ràng buộc gì thêm.