{"raw_statement":[{"iden":"problem statement","content":"There are $N$ slimes lining up in a row. Initially, the $i$\\-th slime from the left has a size of $a_i$.\nTaro is trying to combine all the slimes into a larger slime. He will perform the following operation repeatedly until there is only one slime:\n\n*   Choose two adjacent slimes, and combine them into a new slime. The new slime has a size of $x + y$, where $x$ and $y$ are the sizes of the slimes before combining them. Here, a cost of $x + y$ is incurred. The positional relationship of the slimes does not change while combining slimes.\n\nFind the minimum possible total cost incurred."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $2 \\leq N \\leq 400$\n*   $1 \\leq a_i \\leq 10^9$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $\\ldots$ $a_N$"},{"iden":"sample input 1","content":"4\n10 20 30 40"},{"iden":"sample output 1","content":"190\n\nTaro should do as follows (slimes being combined are shown in bold):\n\n*   (**10**, **20**, 30, 40) → (**30**, 30, 40)\n*   (**30**, **30**, 40) → (**60**, 40)\n*   (**60**, **40**) → (**100**)"},{"iden":"sample input 2","content":"5\n10 10 10 10 10"},{"iden":"sample output 2","content":"120\n\nTaro should do, for example, as follows:\n\n*   (**10**, **10**, 10, 10, 10) → (**20**, 10, 10, 10)\n*   (20, **10**, **10**, 10) → (20, **20**, 10)\n*   (20, **20**, **10**) → (20, **30**)\n*   (**20**, **30**) → (**50**)"},{"iden":"sample input 3","content":"3\n1000000000 1000000000 1000000000"},{"iden":"sample output 3","content":"5000000000\n\nThe answer may not fit into a 32-bit integer type."},{"iden":"sample input 4","content":"6\n7 6 8 6 1 1"},{"iden":"sample output 4","content":"68\n\nTaro should do, for example, as follows:\n\n*   (7, 6, 8, 6, **1**, **1**) → (7, 6, 8, 6, **2**)\n*   (7, 6, 8, **6**, **2**) → (7, 6, 8, **8**)\n*   (**7**, **6**, 8, 8) → (**13**, 8, 8)\n*   (13, **8**, **8**) → (13, **16**)\n*   (**13**, **16**) → (**29**)"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}