Maximizing Tower Height in the Block Stacking Game

SERCOI has recently designed a new block stacking game. Each player is given N rectangular blocks that are numbered consecutively from 1 to N. For each block, its three distinct edges are labeled as the \(a\)-side, \(b\)-side, and \(c\)-side, as shown in the figure below:

The game rules are as follows:

• Grouping: From the \(N\) blocks, you may select a subset and divide them into \(M\) piles (\(1 \le M \le N\)). These piles are labeled as the 1st pile, 2nd pile, …, \(M\)th pile. Each pile must contain at least one block. Moreover, for any two consecutive piles, the rule below must hold: \[ \text{For } 2 \le K \le M, \quad \forall x \in \text{pile } K, \; \forall y \in \text{pile } (K-1), \quad y > x \]
• Stacking within a pile: In each pile, the selected blocks are stacked vertically to form a pillar. The following conditions must be satisfied:
  1. Except for the top block, the top surface of a block touches exactly the bottom surface of the block above it. Moreover, the top surface (a rectangle with sides \(a\) and \(b\)) of the lower block must completely contain the bottom surface of the block above. In mathematical terms, if block \(i\) is immediately below block \(j\) in the same pile, then \[ a_i \ge a_j \quad \text{and} \quad b_i \ge b_j. \]
  2. For any pair of blocks that are in contact (one directly on top of the other), the index of the lower block must be less than that of the upper block.

The final score is determined by the sum of the heights of the \(M\) pillars. Each block’s height is given by its \(c\)-side.

Your task is to devise a block stacking scheme that maximizes the total height of the \(M\) pillars.

Observation: Notice that a valid solution is always to treat every block as a separate pile. This automatically satisfies the stacking conditions because a single block in a pile does not need to satisfy the contact constraints. Hence, the optimal total height is simply \(\sum_{i=1}^{N} c_i\).

inputFormat

The first line contains a single integer \(N\) (\(1 \le N \le 10^5\)), the number of blocks.
Each of the following \(N\) lines contains three positive integers \(a_i\), \(b_i\) and \(c_i\) (\(1 \le a_i, b_i, c_i \le 10^9\)), representing the dimensions of the \(i\)th block. The \(a\)-side and \(b\)-side form the base while the \(c\)-side denotes the height of the block.

outputFormat

Output a single integer, denoting the maximum total height that can be achieved by a valid stacking scheme.

sample

3
3 3 10
2 2 5
1 1 1

16