Giải bài trực tuyến

Hẳn là các bạn không còn xa lạ với nhân vật Mario, anh chàng thợ sửa ống nước nổi tiếng ở vương quốc những cây nấm (Mushroom Kingdom). Một ngày, công chúa Peach quyết định chiêu đãi Mario một bữa buffet nấm thịnh soạn, tuy nhiên để làm cho bữa ăn thú vị hơn nàng đã quyết định biến nó thành một trò chơi dành cho Mario. Trò chơi diễn ra trong N lượt, mỗi lượt một cây nấm sẽ xuất hiện tại một vị trí nào đó trên trục tọa độ, có một chỉ số cân nặng và cung cấp một lượng năng lượng nhất định cho Mario. Mục tiêu của Mario là tìm cách di chuyển để ăn nấm sao cho đạt được năng lượng lớn nhất.

Mario hiện đang đứng ở gốc tọa độ 0 trên trục tọa độ, có cân nặng bằng 0, năng lượng bằng 0 và có thể di chuyển sang trái hoặc sang phải. Có N lượt chơi, mỗi lượt sẽ có một cây nấm xuất hiện. Ở lượt i, cây nấm sẽ xuất hiện ở tọa độ x_i, có chỉ số cân nặng là w_i và chỉ số năng lượng là e_i. Mario có 2 lựa chọn: một là đứng im tại chỗ, cân nặng và năng lượng sẽ không đổi, cây nấm i sẽ biến mất và tiếp tục với lượt i + 1; hai là Mario sẽ di chuyển đến vị trí x_i để ăn cây nấm i, qua đó cân nặng của Mario sẽ trở thành w_i còn năng lượng được cộng thêm e_i. Khi di chuyển, với mỗi bước đi Mario sẽ bị trừ đi một lượng năng lượng bằng với cân nặng hiện tại của mình, nói cách khác nếu Mario di chuyển từ cây nấm thứ j sang cây nấm thứ i thì năng lượng sẽ bị trừ đi w * |x_i - x[j]| (với w là cân nặng hiện tại). Mario không thể di chuyển đến cây nấm thứ i nếu việc di chuyển làm cho năng lượng bị âm (tính đến trước khi ăn cây nấm thứ i).

Bạn hãy giúp Mario tìm một chiến thuật chơi để nhận được nhiều năng lượng nhất nhé.

Input

Dòng đầu tiên gồm số nguyên N, số lượt chơi.

N dòng tiếp theo, mỗi dòng gồm 3 số nguyên x_i, w_i, e_i.

Output

In ra một số nguyên duy nhất là mức năng lượng lớn nhất có thể đạt được.

Giới hạn

Trong tất cả các test, -10⁹ ≤ x_i ≤ 10⁹, 0 ≤ w_i ≤ 1000, 0 ≤ e_i ≤ 10¹²

Subtask 1 (15%): N ≤ 20

Subtask 2 (15%): N ≤ 1000

Subtask 3 (30%): N ≤ 100000, tất cả các giá trị w_i đều bằng nhau

Subtask 4 (40%): N ≤ 100000

Ví dụ

Input:
5
-5 1 4
4 4 10
-3 0 0
-4 4 6
-3 5 10

Output:
15

Giải thích

Lượt 1: Di chuyển từ 0 đến -5 để ăn nấm, năng lượng bằng 0 - 0 * 5 + 4 = 4.

Lượt 2: Bỏ qua.

Lượt 3: Bỏ qua.

Lượt 4: Di chuyển từ -5 đến -4 để ăn nấm, năng lượng bằng 4 - 1 * 1 + 6 = 9.

Lượt 5: Di chuyển từ -4 đến -3 để ăn nấm, năng lượng bằng 9 - 4 * 1 + 10 = 15.