{"problem":{"name":"Snuke Panic (1D)","description":{"content":"Takahashi is trying to catch many Snuke. There are five pits at coordinates $0$, $1$, $2$, $3$, and $4$ on a number line, connected to Snuke's nest. Now, $N$ Snuke will appear from the pits. It is kno","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc266_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc266_d","tags":[],"sample_group":[["3\n1 0 100\n3 3 10\n5 4 1","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."],["3\n1 4 1\n2 4 1\n3 4 1","0\n\nTakahashi cannot catch any Snuke."],["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","2978279323"]],"created_at":"2026-03-03 11:01:14"}}