금광

황금의 땅이라고 불리는 나라가 있다. 이 나라에는 아직 개발하지 않은 금광이 많다. 지도에 금광을 표시할 때는 평면 위의 점으로 나타낸다.

그림 1

각 점 $p_i$에는 양수 또는 음수인 정수 $w_i$가 주어진다. $w_i$는 그 금광을 개발했을 때 생기는 이익이나 손해를 뜻한다. $w_i$가 양수이면 $w_i$만큼 이익이 나고, $w_i$가 음수이면 $|w_i|$만큼 손해가 난다.

금광 개발업자는 $x$축과 $y$축에 평행한 변으로 이루어진 직사각형 모양의 땅 $R$을 사서, $R$에 포함된 금광을 모두 개발한다. 직사각형의 변 위에 놓인 금광도 $R$에 포함된 것으로 본다. 이때 개발 이익은 $R$에 포함된 금광의 $w_i$를 모두 더한 값이다.

개발업자는 개발 이익이 최대가 되는 직사각형 $R$을 찾으려고 한다. 예를 들어 그림 1의 배치에서 개발 이익이 최대가 되는 영역은 그림 2와 같고, 그때의 개발 이익은 7이다.

금광의 좌표와 각 금광을 개발했을 때의 이익 또는 손해가 주어질 때, 직사각형 모양의 땅을 사서 얻을 수 있는 최대 개발 이익을 출력하는 프로그램을 작성하시오.

그림 2

첫째 줄에 금광의 개수 $N$ ($1 \le N \le 3000$)이 주어진다. 이어지는 $N$개 줄에는 금광의 좌표를 나타내는 음이 아닌 두 정수 $x$와 $y$ ($0 \le x, y \le 10^9$), 그리고 그 금광을 개발했을 때의 이익 또는 손해를 나타내는 정수 $w$ ($-10^9 \le w \le 10^9$)가 공백으로 구분되어 주어진다. 금광의 좌표는 모두 서로 다르고, $w > 0$인 금광이 적어도 하나 있다.

한 줄에 금광 개발업자가 직사각형 모양의 땅 $R$을 사서 얻을 수 있는 최대 개발 이익을 출력한다. 계산 과정에서 값이 32비트 정수가 나타낼 수 있는 범위를 넘어 64비트 정수형을 써야 할 수도 있으니 주의하라.