VOMARIO - Mario ở vương quốc những cây nấm

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274861/problem/H
https://codeforces.com/group/FLVn1Sc504/contest/271722/problem/F

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 9 ≤ x i ≤ 10 9 , 0 ≤ w i ≤ 1000, 0 ≤ e i ≤ 10 12

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.

  • Người up: voj
  • Nguồn bài: VNOI Online 2016