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 độ ~x_{i}~, có tổng trữ lượng vàng là ~g_i~, trong mỏ còn có lượng đá đủ để xây dựng đoạn kè có độ dài ~r_{i}~. 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

Input

• Dòng đầu chứa số nguyên dương ~N \leq~ ~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 ~x_{i}~, ~g_{i}~, ~r_{i}~ cách nhau bởi dấu cách (~−10^{9} \leq~ ~x_{1}~ ~<~ ~x_{2}~ ~<~ ⋯ ~<~ ~x_{n}~ ~\leq~ ~10^{9}~; ~0 \leq~ ~g_{i}~, ~r_{i}~ ~\leq~ ~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.

Giới hạn

• 3/6 số điểm ứng với các tests có ~N \leq 5000~
• 3/6 số điểm ứng với các tests có ~10000 \leq N \leq~ ~10^{5}~

Sample Input

4
0 5 1
1 7 2
4 4 1
7 15 1

Sample Output

16