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

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 Codeforces (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 Codeforces. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên Codeforces

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274766/problem/T

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 ≤ 10 5 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 (−10 9 ≤ x1  < x2  < ⋯ < xn  ≤ 10 9 ; 0 ≤ gi, ri   ≤ 10 9 )

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 ≤ 10 5


  • Người up: voj
  • Nguồn bài: Bắc Giang PreVOI 2015