Problem Statement

Takahashi is trying to catch many Snuke.

There are some pits in a two-dimensional coordinate plane, connected to Snuke's nest.

Now, $N$ Snuke will appear from the pits. It is known that the $i$-th Snuke will appear from the pit at coordinates $(X_i,Y_i)$ at time $T_i$, and its size is $A_i$.

Takahashi is at coordinates $(0,0)$ at time $0$ and can do the following two kinds of moves.

• Move at a speed of at most $1$ in the $x$-direction (positive or negative).
• Move at a speed of at most $1$ in the positive $y$-direction.

Moving in the negative $y$-direction is not allowed.

He can catch a Snuke appearing from a pit if and only if he is at the coordinates of that pit exactly when it appears. The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq T_i \leq 10^9$
• $0 \leq X_i,Y_i \leq 10^9$
• $1 \leq A_i \leq 10^9$
• The triples $(T_i,X_i,Y_i)$ are distinct.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
T_1 X_1 Y_1 A_1
T_2 X_2 Y_2 A_2
\vdots
T_N X_N Y_N A_N

Output

Print the answer as an integer.