문제2018--복어 채집 (Small)

2018: 복어 채집 (Small)

[만든사람 : jbs33_PJW]
시간제한 : 1.000 sec  메모리제한 : 128 MiB

문제 설명

jbs33_LDH는 복어를 무척이나 좋아한다.


귀엽다.
그런 그에게 복어를 채집할 수 있는 기회가 왔다.
단, 무턱대고 잡기에는 바다가 너무 넓기 때문에, 몇 가지 정보를 토대로 구역을 정해서 잡을 수 있다.


복어를 잡기 위해, jbs33_LDH는 현재 위치에 있는 복어의 수를 조사하여 나타냈다.
하지만 바다가 깨끗하지 않아 쓰레기들이 있었고, jbs33_LDH는 이를 수치화하기 위해 쓰레기 1개를 복어 -1마리로 생각했다.
또한, 단 하나의 그물만 사용할 수 있고, 이는 직사각형 모양으로만 나타낼 수 있다.

점은 복어의 위치, 왼쪽의 숫자는 복어의 수를 의미한다.

하늘색 직사각형은 복어를 최대로 잡을 수 있는 구역이다.
jbs33_LDH는 복어를 최대한 많이 잡으려고 한다. 가장 많이 잡을 수 있는 복어의 수를 구하자.
아예 잡지 않는 경우도 하나의 방법이 될 수 있다.


입력 설명

첫 번째 줄에 정보의 개수 N이 주어진다.
(1 ≤ N ≤ 100000)
두 번째 줄부터 N개의 줄로 정보의 위치 x,y와 복어의 마리수 w가 주어진다.
(1 ≤ x,y ≤ 300, -10000 ≤ w ≤ 10000)

출력 설명

최대로 잡을 수 있는 복어의 수를 출력한다.

입력 예시 Copy

4
2 2 3
3 4 5
6 3 -6
5 1 4

출력 예시 Copy

12 

게시판

작성자제목(댓글)
글이 없습니다.

출처/분류