Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vomario


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 độ xi, có chỉ số cân nặng là wi và chỉ số năng lượng là ei. 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í xi để ăn cây nấm i, qua đó cân nặng của Mario sẽ trở thành wi còn năng lượng được cộng thêm ei. 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 * |xi - 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 xi, wi, ei.

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, -109xi ≤ 109, 0 ≤ wi ≤ 1000, 0 ≤ ei ≤ 1012

Subtask 1 (15%): N ≤ 20

Subtask 2 (15%): N ≤ 1000

Subtask 3 (30%): N ≤ 100000, tất cả các giá trị wi đề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.


Được gửi lên bởi:VOJ Team
Ngày:2015-12-25
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 PAS-GPC PAS-FPC
Nguồn bài:VNOI Online 2016

hide comments
2019-11-15 09:25:45
bài cơ bản IT đoạn thẳng
2019-06-28 19:55:24
sai test ví dụ AC ? :D ?
2016-08-27 13:00:47
Toàn test to @@ Tràn số 0 điểm
2016-02-22 10:06:46 Lương Ðức Tuấn Ðạt
bài này hay

Last edit: 2016-02-22 10:07:06
2016-02-01 09:16:23
THAM KHAO http://codevnspoj.blogspot.com/
2016-01-03 15:35:20
bài này Mario có cần phải đi qua hết n nấm ko vậy?
2015-12-31 11:08:12 The Flash
bài này qui hoach động n^2 sao mãi mà vần cứ zero T_T
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.