#abc266d. [abc266_d]Snuke Panic (1D)

[abc266_d]Snuke Panic (1D)

Problem Statement

Takahashi is trying to catch many Snuke.

There are five pits at coordinates 00, 11, 22, 33, and 44 on a number line, connected to Snuke's nest.

Now, NN Snuke will appear from the pits. It is known that the ii-th Snuke will appear from the pit at coordinate XiX_i at time TiT_i, and its size is AiA_i.

Takahashi is at coordinate 00 at time 00 and can move on the line at a speed of at most 11.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate 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

  • 1leqNleq1051 \\leq N \\leq 10^5
  • 0<T1<T2<ldots<TNleq1050 < T_1 < T_2 < \\ldots < T_N \\leq 10^5
  • 0leqXileq40 \\leq X_i \\leq 4
  • 1leqAileq1091 \\leq A_i \\leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN T1T_1 X1X_1 A1A_1 T2T_2 X2X_2 A2A_2 vdots\\vdots TNT_N XNX_N ANA_N

Output

Print the answer as an integer.


Sample Input 1

3
1 0 100
3 3 10
5 4 1

Sample Output 1

101

The optimal strategy is as follows.

  • Wait at coordinate 00 to catch the first Snuke at time 11.
  • Go to coordinate 44 to catch the third Snuke at time 55.

It is impossible to catch both the first and second Snuke, so this is the best he can.


Sample Input 2

3
1 4 1
2 4 1
3 4 1

Sample Output 2

0

Takahashi cannot catch any Snuke.


Sample Input 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

Sample Output 3

2978279323