2018: 복어 채집 (Small)
[만든사람 : jbs33_PJW]
문제 설명
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)
(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