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 \times |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

Giới hạn

Trong tất cả các test, - ~10^{9} \leq x_i \leq 10^{9}~, ~0 \leq w_i \leq 1000~, ~0 \leq e_i \leq 10^{12}~

• Subtask ~1~ ~(15\%)~: ~N \leq 20~
• Subtask ~2~ ~(15\%)~: ~N \leq 1000~
• Subtask ~3~ ~(30\%)~: ~N \leq 100000~, tất cả các giá trị ~w_i~ đều bằng nhau
• Subtask ~4~ ~(40\%)~: ~N \leq 100000~

Sample Input

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

Sample Output

15

Note

• Lượt ~1~: Di chuyển từ ~0~ đến ~-5~ để ăn nấm, năng lượng bằng ~0~ - ~0 \times 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 \times 1 + 6 = 9~.
• Lượt ~5~: Di chuyển từ ~-4~ đến ~-3~ để ăn nấm, năng lượng bằng ~9~ - ~4 \times 1 + 10 = 15~.