{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"赵老师降落在火星上的一片森林中,他想要带一些资源回地球进行研究\u003cbr\u003e\n森林由两行组成,每行可分为n个连续空格。对于每个空格,赵老师都知道资源在这个空格中的生长速度(即每分钟在这个空格中生长多少克资源)。\u003cbr\u003e\n赵老师可以用1分钟从一个格子移动到另一个相邻的格子中。赵老师不能离开这片森林。\u003cbr\u003e\n如果两个单元格共用一个边,则认为它们是相邻的。\u003cbr\u003e\n当赵老师进入某个格子中时,他将立即收集完所有生长在那里的资源。\u003cbr\u003e\n赵老师从左上角的格子开始他的旅程。赵老师每分钟都必须移动到相邻的格子中,他不能等待资源生长。\u003cbr\u003e\n他只想进入每个格子一次,并最大化收集到的资源的总重量。\u003cbr\u003e\n最初,所有格子中的资源都是0。注意,赵老师不需要返回起始格子。\u003cbr\u003e\n求出最大总重量"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个正整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u0026nbsp;(1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 3·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e)\u003c/span\u003e — 格子的长度.\u003c/p\u003e\n\u003cp\u003e第二行有 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e个正整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u0026nbsp;(1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e)\u003c/span\u003e — 第一行中每个格子的生长速率.\u003c/p\u003e\n\u003cp\u003e第三行包含 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 个正整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u0026nbsp;(1 ≤ \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e)\u003c/span\u003e — 第二行中每个格子的生长速率.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数 — 赵老师能采集到的最大资源量. 注意,每个格子赵老师最多只能经过一次!\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e3\u003cbr\u003e1 2 3\u003cbr\u003e6 5 4\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e70\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e3\u003cbr\u003e1 1000 10000\u003cbr\u003e10 100 100000\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e543210\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e第一个样例中,赵老师的路线如下图: \u003c/p\u003e\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" SRC\u003d\"CDN_BASE_URL/f15cb8f4ec9af78366c128cd12d1d073?v\u003d1548725652\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \n\u003c/center\u003e 因此,他收集的资源量为 \n\u003cspan class\u003d\"tex-span\"\u003e0·1 + 1·2 + 2·3 + 3·4 + 4·5 + 5·6 \u003d 70\u003c/span\u003e.\n\u003cp\u003e第二个样例中,赵老师的路线为: \u003c/p\u003e\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" SRC\u003d\"CDN_BASE_URL/17fc6fdb43a74bcfd210a1f4e0b10410?v\u003d1548725652\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \n\u003c/center\u003e 因此,他收集到的资源为 \n\u003cspan class\u003d\"tex-span\"\u003e0·1 + 1·10 + 2·100 + 3·1000 + 4·10000 + 5·100000 \u003d 543210\u003c/span\u003e."}}]}