{"raw_statement":[{"iden":"problem statement","content":"Takahashi is trying to catch many Snuke.\nThere are five pits at coordinates $0$, $1$, $2$, $3$, and $4$ on a number line, connected to Snuke's nest.\nNow, $N$ Snuke will appear from the pits. It is known that the $i$\\-th Snuke will appear from the pit at coordinate $X_i$ at time $T_i$, and its size is $A_i$.\nTakahashi is at coordinate $0$ at time $0$ and can move on the line at a speed of at most $1$.  \nHe can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.  \nThe time it takes to catch a Snuke is negligible.\nFind the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^5$\n*   $0 < T_1 < T_2 < \\ldots < T_N \\leq 10^5$\n*   $0 \\leq X_i \\leq 4$\n*   $1 \\leq A_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$T_1$ $X_1$ $A_1$\n$T_2$ $X_2$ $A_2$\n$\\vdots$\n$T_N$ $X_N$ $A_N$"},{"iden":"sample input 1","content":"3\n1 0 100\n3 3 10\n5 4 1"},{"iden":"sample output 1","content":"101\n\nThe optimal strategy is as follows.\n\n*   Wait at coordinate $0$ to catch the first Snuke at time $1$.\n*   Go to coordinate $4$ to catch the third Snuke at time $5$.\n\nIt is impossible to catch both the first and second Snuke, so this is the best he can."},{"iden":"sample input 2","content":"3\n1 4 1\n2 4 1\n3 4 1"},{"iden":"sample output 2","content":"0\n\nTakahashi cannot catch any Snuke."},{"iden":"sample input 3","content":"10\n1 4 602436426\n2 1 623690081\n3 3 262703497\n4 4 628894325\n5 3 450968417\n6 1 161735902\n7 1 707723857\n8 2 802329211\n9 0 317063340\n10 2 125660016"},{"iden":"sample output 3","content":"2978279323"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}