Treasure Pyramid Excavation

JP has taken up a new game – treasure hunting. In the game there are \(n\) treasures buried in an infinite 2D grid. The \(i\)th treasure has a value \(P_i\) and is located at coordinates \((x_i,y_i)\). In this grid a cell \((x,y)\) can be excavated if and only if it satisfies one of the following conditions:

1. \(y=-1\); or
2. the three cells \( (x-1,y+1)\), \( (x,y+1)\) and \( (x+1,y+1)\) have all been excavated.

Excavating a cell costs \(1\) unit. When a treasure is excavated (i.e. its cell is excavated), its value is obtained. Note that you may choose not to excavate any cell (in which case the profit is \(0\)).

Your task is to help JP determine the maximum profit achievable, where profit is defined as the total value of excavated treasures minus the total excavation cost.

Note on the excavation rules. The rule forces that if you excavate a cell that is not in row \(y=-1\) then you must also excavate its three "support" cells in row \(y+1\). Hence any feasible excavation plan is an (inverted) pyramid structure starting from some contiguous interval of cells in row \(y=-1\) and then, in each subsequent row \(y\lt-1\), a (possibly smaller) contiguous interval is excavated so that for every excavated cell, its three cells above have been excavated.

For example, to excavate the cell \((0,-2)\) you must first excavate three cells in row \(y=-1\): \((-1,-1)\), \((0,-1)\) and \((1,-1)\); then you may excavate \((0,-2)\). The cost incurred is the total number of cells excavated, and you only get the value of treasure in cells where treasures are buried.

Determine the maximum profit JP can get.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 100\)), the number of treasures.

Each of the following \(n\) lines contains three integers \(x_i\), \(y_i\) and \(P_i\), indicating that there is a treasure of value \(P_i\) at coordinates \((x_i,y_i)\). It is guaranteed that all \(x_i\) and \(y_i\) fit in a 32-bit signed integer. Note that by the rules, a cell can be excavated only if its \(y\)-coordinate is \(-1\) or below. (You may assume that all treasures lie in rows \(y\le -1\).)

outputFormat

Output a single integer representing the maximum profit (total treasure value minus excavation cost) that JP can achieve. If no excavation yields a positive profit, output \(0\).

sample

1
0 -2 10

6