Một viện nghiên cứu khí tượng thủy văn đặt ~N~ trạm quan trắc được đánh số từ ~1~ đến ~N~ dọc theo một con sông lớn để theo dõi mực nước và thu thập dữ liệu tài nguyên. Vị trí các trạm quan trắc được biểu diễn trên một trục số. Trạm thứ ~i~ nằm ở vị trí ~x_i~, chứa ~g_i~ đơn vị dữ liệu và có ~r_i~ đơn vị đá dùng để làm kè chống lũ. Không có hai trạm nào nằm cùng vị trí.

Để bảo vệ các trạm quan trắc trong mùa mưa lũ, viện nghiên cứu muốn xây tối đa ~K~ đoạn kè rời nhau dọc bờ sông. Mỗi đoạn kè có thể có độ dài khác nhau. Chi phí để xây một đoạn kè từ vị trí ~x_a~ đến vị trí ~x_b~ là ~x_b - x_a~ ~(x_a < x_b)~ đơn vị đá và số đá này chỉ được lấy từ các trạm có vị trí thuộc đoạn ~[x_a, x_b]~. Nói cách khác, nếu muốn xây một đoạn kè từ vị trí ~x_a~ đến ~x_b~ thì tổng số đơn vị đá của tất cả các trạm nằm trong đoạn kè này phải không nhỏ hơn ~x_b - x_a~. Mỗi đoạn kè sẽ bảo vệ dữ liệu của các trạm bên trong chúng và mỗi trạm chỉ thuộc nhiều nhất một đoạn kè.

Yêu cầu: Hãy tìm phương án chọn tối đa ~K~ đoạn kè sao cho tổng giá trị dữ liệu được bảo vệ là lớn nhất.

Input

• Dòng đầu chứa hai số nguyên dương ~N~ và ~K~ ~(1 \le N \le 2000, 1 \le K \le 10)~.

• ~N~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên ~x_i, g_i, r_i~ biểu thị vị trí, lượng dữ liệu và số đơn vị đá của trạm thứ ~i~ ~(|x_i| \le 10^9, 1 \le g_i \le 10^9, 1 \le r_i \le 10^6)~.

Output

Một số nguyên duy nhất là tổng giá trị dữ liệu lớn nhất có thể được bảo vệ.

Scoring

Sample Input 1

6 2
20 100 4
0 100 3
1 10 1
9 10 1
11 80 1
12 80 4

Sample Output 1

370

Sample Input 2

6 4
20 100 4
0 100 3
1 10 1
9 10 1
11 80 1
12 80 4

Sample Output 2

380

Notes

Trong ví dụ thứ nhất, được xây tối đa ~K=2~ đoạn kè, ta xây như sau:

• Xây đoạn kè thứ nhất ~[0,1]~ chứa trạm ~2,3~: tổng dữ liệu được bảo vệ là ~110~.

• Xây đoạn kè thứ hai ~[11,20]~ chứa trạm ~1,5,6~: tổng dữ liệu được bảo vệ là ~260~.

Tổng dữ liệu được bảo vệ của ~2~ đoạn kè là ~370~, đây là giá trị lớn nhất có thể.

Trong ví dụ thứ hai, được xây tối đa ~K=4~ đoạn kè, ta chỉ cần xây ~3~ đoạn kè là đủ bảo vệ dữ liệu của toàn bộ ~N~ trạm:

• Xây đoạn kè thứ nhất ~[0,1]~ chứa trạm ~2,3~: tổng dữ liệu được bảo vệ là ~110~.

• Xây đoạn kè thứ hai ~[9,10]~ chứa trạm ~4~: tổng dữ liệu được bảo vệ là ~10~.

• Xây đoạn kè thứ ba ~[11,20]~ chứa trạm ~1,5,6~: tổng dữ liệu được bảo vệ là ~260~.

Tổng dữ liệu được bảo vệ của ~3~ đoạn kè là ~380~, đây là giá trị lớn nhất có thể.