불도저

JOI 왕국은 금 생산으로 유명하다. JOI 왕국은 매년 한 번 불도저를 사용해 금을 채굴한다.

JOI 왕국의 땅은 xy좌표평면으로 표현된다. 땅에는 N개의 지점이 있다. i번째 지점 (1 ≤ i ≤ N)은 (Xi, Yi)이다. 각 지점에는 금 또는 암석 중 하나만 있다.

i번째 지점에 금이 있으면 한 번 채굴할 때 가치 Vi의 금을 얻는다. i번째 지점에 암석이 있으면 한 번 채굴할 때 암석을 얻고, 이를 버리는 비용은 Ci이다.

불도저로 채굴하는 방법은 다음과 같다. 먼저 xy평면에서 서로 평행한 두 직선을 고른다. 그런 다음 두 평행선 사이의 영역에 있는 모든 금과 암석을 각각 한 번씩 채굴한다(두 직선 위에 놓인 금이나 암석도 포함한다).

JOI 왕국의 이익은 채굴 영역에 있는 금의 가치 합에서 같은 영역에 있는 암석을 버리는 비용 합을 뺀 값이다. JOI 왕국의 이익을 최대로 만들고자 한다.

JOI 왕국의 최대 이익을 계산하는 프로그램을 작성하라.

다음 데이터를 표준 입력에서 읽는다.

• 첫째 줄에 지점의 수 N이 주어진다.

• 다음 N개 줄의 i번째 줄 (1 ≤ i ≤ N)에는 세 정수 Xi, Yi, Wi가 공백으로 구분되어 주어진다.

  • Wi ≥ 1이면 i번째 지점 (Xi, Yi)에 금이 있다. 한 번 채굴할 때 가치 Vi = Wi의 금을 얻는다.
  • Wi ≤ −1이면 i번째 지점 (Xi, Yi)에 암석이 있다. 한 번 채굴할 때 암석을 얻고, 이를 버리는 비용은 Ci = −Wi이다.
  • Wi ≠ 0이다.

표준 출력에 한 줄을 출력한다. JOI 왕국의 최대 이익을 출력한다.

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ N ≤ 2 000.
• −1 000 000 000 ≤ Xi ≤ 1 000 000 000 (1 ≤ i ≤ N).
• −1 000 000 000 ≤ Yi ≤ 1 000 000 000 (1 ≤ i ≤ N).
• 1 ≤ |Wi| ≤ 1 000 000 000.
• (Xi, Yi) ≠ (Xj, Yj) (1 ≤ i < j ≤ N).