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

BGMINE - Xây đập giữ vàng

Trên một con đường biểu diễn như trục số thực có n mỏ vàng đánh số từ 1 tới n. Mỏ thứ  i nằm ở tọa độ xi, có tổng trữ lượng vàng là gi, trong mỏ còn có lượng đá đủ để xây dựng đoạn kè có độ dài ri. Trong mùa mưa lũ, việc phòng chống ngập cho các mỏ trở nên cấp thiết và rất khó khăn trong việc vận chuyển vật liệu xây kè. Vì vậy, Chính phủ muốn  dùng đá ở một dãy mỏ liên tiếp để xây dựng một đoạn kè liên tục bảo vệ tất cả các mỏ đó. Ta có thể coi cửa các mỏ vàng rất nhỏ, nên dù chỉ nằm ở đầu đoạn kè thì mỏ vẫn được an toàn.

Yêu cầu: Hãy giúp chính phủ xác định đoạn kè có thể xây dựng với tổng trữ lượng vàng trong các mỏ được bảo vệ là lớn nhất.

Input

  • Dòng đầu chứa số nguyên dương  n ≤ 105  là số lượng mỏ vàng.
  • n dòng tiếp theo, dòng thứ i chứa ba số nguyên xi, gi, ri cách nhau bởi dấu cách (−109  ≤ x1  < x2  < ⋯ < xn  ≤ 109; 0 ≤ gi, ri   ≤ 109)

Output

  • Một số nguyên duy nhất là tổng trữ lượng vàng lớn nhất trong các mỏ được bảo vệ theo phương án tìm được.

Example

Input:

4

0 5 1

1 7 2

4 4 1

7 15 1

Output: 16

Chú ý:

  • 3/6 điểm ứng với các tests có n ≤ 5000 
  • 3/6 số điểm ứng với các tests có 10000 ≤ n ≤ 105

Được gửi lên bởi:VOJ Team
Ngày:2015-12-09
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:Bắc Giang PreVOI 2015

hide comments
2017-08-07 03:02:45
trau cung ac de vl
2016-12-13 00:35:15


Last edit: 2016-12-13 00:35:24
2016-09-27 03:07:06
Code:
http://shink.in/hYpfo
2016-09-13 11:10:47
Chặt nhị phân sai :D
2016-08-03 03:59:47
ai mà 85 là nghĩ thiếu 1 chỗ rồi :3
2016-02-09 15:32:27 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/26/spoj-bgmine/

Last edit: 2016-09-27 11:11:02
2016-02-01 09:15:50
THAM KHAO http://codevnspoj.blogspot.com/
2015-12-16 08:15:25 The Flash
cần lắm một hướng dẫn
2015-12-14 08:00:17 Lê Trần Hữu Ðắc
??
2015-12-14 04:06:38
tran le huu dac
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.