시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 5 5 5 100.000%

문제

한 도시에 건물들을 지으려고 한다. 각각의 건물들을 지었을 경우의 이익이 있는데, 최대한 많은 이익을 얻기 위해 건물을 지으려고 한다. 어떤 좌표에 건물을 지었을 때, 이 점을 기준으로 평면을 네 구간으로 나눌 수 있다. 쉽게 생각하면 좌표평면상에서 제 1, 2, 3, 4 사분면을 생각하면 된다. 아래 그림이 각 구간과 구간의 번호이다.

위의 그림에서 가운데에 건물을 지은 경우이고, 각각의 번호가 이 건물을 기준으로 한 구간의 번호를 나타낸다.
  도시의 미관을 생각해 보았을 때, 한 건물의 구간 1과 구간 2에 건물이 있는 경우나 1, 4에 있는 경우, 2, 3에 있는 경우, 3, 4에 있는 경우는 아름답지 않다. 즉, 1, 3 구간에 있거나 2, 4 구간에 있어야 한다.
  이와 같은 조건을 만족하면서 건물들을 지었을 때, 가능한 최대의 이익을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 건물의 개수를 나타내는 자연수 N(1≤N≤1,000)이 주어진다. 다음 N개의 줄에는 건물을 지을 x, y(1≤x, y≤1,000,000,000) 좌표와 그 건물을 지었을 때의 이익 c(1≤c≤50,000)가 주어진다.

출력

첫째 줄에 최대 이익을 출력한다.

예제 입력

4
1 1 2
2 5 4
4 6 2
5 2 5

예제 출력

9

힌트