2296번 - 건물짓기

한 도시에 건물들을 지으려고 한다. 각각의 건물들을 지었을 경우의 이익이 있는데, 최대한 많은 이익을 얻기 위해 건물을 지으려고 한다. 어떤 좌표에 건물을 지었을 때, 이 점을 기준으로 평면을 네 구간으로 나눌 수 있다. 쉽게 생각하면 좌표평면상에서 제 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)가 주어진다. 서로 다른 두 건물이 같은 x좌표나 같은 y좌표를 가지는 경우는 없다.

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