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.|

VMPIZZA - Pizza

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/vmpizza


Linh đang sống trên tầng 5 ở East Campus, một trong những kí túc lâu đời nhất của MIT. Một điểm bất tiện của kí túc này là không có thang máy, dẫn đến sự đi lại khó khăn.

Sau một buổi làm việc căng thẳng, Linh quyết định đặt pizza thay cho bữa tối. Để thay đổi khẩu vị, cậu đặt N pizza tại N cửa hàng khác nhau. Pizza thứ i được chở đến tại thời điểm ti, cung cấp ai năng lượng nếu ăn ngay. Tuy nhiên, Pizza sẽ mất dần độ nóng hổi cũng như năng lượng theo thời gian: qua mỗi thời điểm, pizza thứ i mất bi năng lượng.

Linh biết trước thời điểm và giá trị của N loại pizza, và cậu muốn đạt được càng nhiều năng lượng càng tốt. Mỗi lần, Linh có thể chạy xuống nhận pizza, mang về phòng và ăn hết số pizza trong thời gian không đáng kể. Tuy nhiên, nên nhớ rằng Linh sống ở tầng 5, mỗi chuyến đi sẽ tiêu tốn của cậu B năng lượng. Linh không thích phí phạm đồ ăn (mặc dù đã sống gần 2 năm ở Mỹ), cậu sẽ luôn ăn hết pizza, kể cả khi năng lượng của nó xuống dưới 0 (khi ăn thì Linh sẽ bị cộng thêm một lượng âm năng lượng, hay nói cách khác là bị giảm năng lượng).

Xác định lượng năng lượng tối đa Linh sẽ có với chiến thuật chạy tối ưu.

Input

Dòng 1: 2 số nguyên NB.

Dòng 2..N + 1: mỗi dòng chứa 3 số nguyên ti, ai, bi (1 ≤ ti, ai, bi ≤ 105)

Output

Một dòng duy nhất: năng lượng tối đa với chiến thuật chạy tối ưu. Kết quả nằm trong phạm vi số nguyên 64-bit (int64 trên Pascal hoặc long long trên C++).

Giới hạn

  • 1 ≤ N ≤ 105.
  • 1 ≤ B ≤ 105.
  • Trong ít nhất 30% số test, tương ứng với 30% số điểm, N ≤ 1000
  • Trong quá trình thi, bài của bạn chỉ được chấm với 2 test ví dụ. Kết quả sẽ hiện 100 nếu bài của bạn chạy đúng cả 2 test.

Ví dụ

Input 1:

2 5
1 4 1
2 6 1

Output 1:

4

Input 2:

2 3
1 1 100
2 10 1

Output 2:

5

Giải thích

  • Trong test 1, phương án tối ưu là chạy xuống 1 lần tại thời điểm 2, lấy cả 2 pizza lên và ăn ngay. Kết quả = (4 - 1) + (6 - 0) - 5 = 4.
  • Trong test 2, phương án tối ưu là chạy xuống 2 lần tại thời điểm 1 và 2. Kết quả = (1 - 0) - 3 + (10 - 0) - 3 = 5.

Được gửi lên bởi:VOJ Team
Ngày:2015-07-23
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:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VM15 - Nguyễn Vương Linh

hide comments
2019-08-01 08:17:30
tham lam AC moi la ,BIT+DP---->AC
2019-08-01 07:36:54
tham lam AC
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.