Chọn hình vuông

Có $N$ điểm trên mặt phẳng vô hạn, điểm thứ $i$ có tọa độ nguyên $(x_i,y_i)$ và giá trị nguyên $c_i$. Bạn cần chọn một hình vuông có các cạnh song song với trục tọa độ sao cho góc trái dưới và góc phải trên nằm trên đường thẳng $y=x$, tức là hình vuông gồm các điểm $(x,y)$ với $l\le x\le r$ và $l\le y\le r$ (với $l\le r$). Điểm của cách chọn bằng tổng giá trị $c_i$ của tất cả các điểm nằm trong và trên cạnh của hình vuông đó trừ đi độ dài $1$ cạnh của hình vuông (bằng $r-l$). Chú ý có thể chọn hình vuông cạnh là $0$, tức là bạn chọn $1$ vị trí bất kì nằm trên đường thẳng $y=x$.

Yêu cầu: Bạn cần tính số điểm cao nhất có thể nhận được sau khi chọn một hình vuông bất kì.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương $N$ $(1\le N\le {10}^5)$ là số điểm trên mặt phẳng.
• $N$ dòng sau, mỗi dòng gồm $3$ số nguyên $x_i,y_i,c_i$ $(0\le x_i,y_i\le {10}^9,-{10}^6\le c_i\le {10}^6)$ là tọa độ và giá trị của điểm thứ $i$.

Dữ liệu ra

In ra điểm lớn nhất có thể đạt được.

Ràng buộc

• $1\le N\le {10}^5$.
• $0\le x_i,y_i\le {10}^9$.
• $-{10}^6\le c_i\le {10}^6$.

Subtasks

• Subtask 1 ($30\%$ số test): $N\le 400$; các tọa độ nhỏ hơn $400$.
• Subtask 2 ($30\%$ số test): $N\le 1000$; các tọa độ nhỏ hơn $1000$.
• Subtask 3 ($30\%$ số test): các tọa độ $x_i,y_i$ nhỏ hơn ${10}^5$.
• Subtask 4 ($10\%$ số test): không có điều kiện gì thêm.

Ví dụ