In the anime《A Certain Scientific Railgun》《とある科学の超電磁砲》, the protagonist – Misaka has the power to control electricity and one of her most iconic attacks is “Railgun”, which is shooting a coin as a projectile that travels three times the speed of sound.

Figure. From Wikipedia

To test her strength, an infinitely large wall which can be viewed as a 2D Cartesian plane filled with $N$ targets is prepared. Each target can be described by a coordinate position $(X_i,Y_i)$ and a range $R_i$. There can be more than 1 target at the same position. Misaka will then choose a point $(X_0, Y_0)$ and fire a "Railgun" at that position.

For the $i^{th}$ target, the point Misaka gets is $$\begin{cases} (R_i-|X_i-X_0|)\times(R_i-|Y_i-Y_0|) &\text{if } |X_i-X_0| \le R_i &\text{and } |Y_i-Y_0| \le R_i \\ 0 &\text{otherwise} \end{cases}$$ The total points she gets is the sum of the points she gets in each target.

To illustrate, if $(X_0,Y_0)=(0,3)$ and the target is located at $(1,2)$ with range $3$, Misaka can get $(3-|1-0|)\times(3-|2-3|)=4$ points.

As one of the most powerful espers and genius in mathematics and science, she immediately found a position that could achieve the maximum points. (And she is 14, Look at you)

Now you want to find the maximum total points she can obtain.

Input

The first line of input contains one integer, $N$.
The next $N$ lines of input contains three integers, the $i^{th}$ line contains $X_i, Y_i$ and $R_i$.

Output

Output a single integer, the maximum total points Misaka can get.

Constraint

For all cases, $1 \le N \le 10^6, -100 \le X_i, Y_i \le 100, 1 \le R_i \le 100$
Subtask 1 (15%): $1 \le N \le 1000$
Subtask 2 (15%): $1 \le R_i \le 3$
Subtask 3 (30%): All $X_i$ are equal, i.e. $X_1=X_2=...=X_N$
Subtask 4 (40%): No additional constraints