Building Profit Plan

There are several candidate buildings in a city. Each candidate has a distinct x-coordinate and y-coordinate, and building it gives a fixed profit. Choose some of the buildings so that the total profit is as large as possible.

For any chosen building, divide the plane into four regions around it. Region 1 contains points with both larger x and larger y. Region 2 contains points with smaller x and larger y. Region 3 contains points with both smaller x and smaller y. Region 4 contains points with larger x and smaller y.

For the city to look good, every chosen building must satisfy this condition. From that building's point of view, other chosen buildings must not appear in any adjacent pair of regions: 1 and 2, 1 and 4, 2 and 3, or 3 and 4. In other words, the other chosen buildings must lie only in the diagonal regions 1 and 3, or only in the diagonal regions 2 and 4. Having buildings in only one region is also allowed.

Find the maximum total profit obtainable while satisfying this condition.

The first line contains the number of candidate buildings N. (1 <= N <= 1,000)

Each of the next N lines contains three integers x, y, and c: the coordinates of a candidate building and the profit gained by building it. (1 <= x, y <= 1,000,000,000, 1 <= c <= 50,000)

No two different buildings have the same x-coordinate, and no two different buildings have the same y-coordinate.

Output the maximum profit obtainable by choosing buildings that satisfy the condition.