Giải bài trực tuyến

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⁵  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⁹  ≤ x1  < x2  < ⋯ < xn  ≤ 10⁹; 0 ≤ gi, ri   ≤ 10⁹)

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⁵