{"problem":{"name":"Three Coins","description":{"content":"$N$ cells are arranged in a row. The cells are numbered $1$ through $N$ from left to right. Initially, all cells are empty. You can perform the following two types of operation arbitrary number of tim","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc050_b"},"statements":[{"statement_type":"Markdown","content":"$N$ cells are arranged in a row. The cells are numbered $1$ through $N$ from left to right.\nInitially, all cells are empty. You can perform the following two types of operation arbitrary number of times in arbitrary order:\n\n*   Choose three **consecutive** empty cells, and put a coin on each of the three cells.\n*   Choose three **consecutive** cells with coins, and remove all three coins on the chosen cells.\n\nAfter you finish performing operations, if the $i$\\-th cell contains a coin, you get $a_i$ points. Your score is the sum of all points you get from the cells with coins.\nCompute the maximum possible score you can earn.\n\n## Constraints\n\n*   $3 \\leq N \\leq 500$\n*   $-100 \\leq a_i \\leq 100$\n*   All values in the input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$\n$a_2$\n$:$\n$a_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc050_b","tags":[],"sample_group":[["4\n1\n2\n3\n4","9\n\nWe represent a cell with a coin as `o` and a cell without a coin as `.` (a dot). One optimal way is as follows:\n`....` $\\rightarrow$ `.ooo`\nWe get $2 + 3 + 4 = 9$ points this way."],["6\n3\n-2\n-1\n0\n-1\n4","6\n\nOne optimal way is as follows:\n`......` $\\rightarrow$ `ooo...` $\\rightarrow$ `oooooo` $\\rightarrow$ `o...oo`\nWe get $3 + (-1) + 4 = 6$ points this way."],["10\n-84\n-60\n-41\n-100\n8\n-8\n-52\n-62\n-61\n-76","0"]],"created_at":"2026-03-03 11:01:14"}}