건물 짓기

도시에 지을 수 있는 건물 후보가 여러 개 있다. 각 후보 건물은 서로 다른 x좌표와 y좌표를 가지며, 그 건물을 지으면 정해진 이익을 얻는다. 이익의 합이 최대가 되도록 일부 건물을 선택해 지으려고 한다.

어떤 선택된 건물을 기준으로 평면을 네 구역으로 나눈다. 구역 1은 기준 건물보다 x좌표와 y좌표가 모두 큰 곳, 구역 2는 x좌표는 작고 y좌표는 큰 곳, 구역 3은 x좌표와 y좌표가 모두 작은 곳, 구역 4는 x좌표는 크고 y좌표는 작은 곳이다.

도시의 미관을 위해, 모든 선택된 건물은 다음 조건을 만족해야 한다. 한 건물을 기준으로 보았을 때 다른 선택된 건물들이 인접한 두 구역 쌍인 1과 2, 1과 4, 2와 3, 3과 4에 동시에 존재하면 안 된다. 즉, 기준 건물에서 본 다른 선택된 건물들은 대각선 방향인 1과 3에만 있거나, 대각선 방향인 2와 4에만 있어야 한다. 한쪽 구역에만 있는 경우도 조건을 만족한다.

조건을 만족하도록 건물들을 선택했을 때 얻을 수 있는 최대 이익을 구하시오.

첫째 줄에 건물 후보의 개수 N이 주어진다. (1 <= N <= 1,000)

다음 N개의 줄에는 건물을 지을 위치의 좌표 x, y와 그 건물을 지었을 때의 이익 c가 주어진다. (1 <= x, y <= 1,000,000,000, 1 <= c <= 50,000)

서로 다른 두 건물이 같은 x좌표를 가지는 경우는 없고, 같은 y좌표를 가지는 경우도 없다.

조건을 만족하도록 건물들을 선택했을 때 얻을 수 있는 최대 이익을 출력한다.