{"trustable":false,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"cocktail 和 XiaoYang 在玩植物大战僵尸。在游戏中,XiaoYang 在花园里种植植物来防御 cocktail 的僵尸。\n\nXiaoYang 家种了 `n` 棵植物排成一排。从西向东,植物依次被编号为1-n,并且第 `i` 棵植物在房屋以东 `i` 米处。每棵植物有防御值 d\u003csub\u003ei\u003c/sub\u003e 和生长值 a\u003csub\u003ei\u003c/sub\u003e。最开始的时候,所有植物的 d\u003csub\u003ei\u003c/sub\u003e \u003d 0。\n\nXiaoYang 使用一个机器人来给植物浇水。机器人最开始的时候在房子里。在一步浇水过程中,XiaoYang 会选择一个方向(西或东)机器人会沿着这个方向移动1米。在移动之后,如果第 `i` 棵植物在机器人的位置处,机器人将给植物浇水,然后 a\u003csub\u003ei\u003c/sub\u003e 将被加进 d\u003csub\u003ei\u003c/sub\u003e。由于机器人中的水是有限的,机器人最多只能移动 `m` 步。\n\n花园的防御值被定义为 `min { d`\u003csub\u003ei\u003c/sub\u003e\u0026nbsp;` | 1 ≤ i ≤ n}`。XiaoYang 需要你的帮助来最大化花园的防御值来战胜 cocktail。\n\n请注意:\n\n- 每次机器人浇水前必须移动。\n- 机器人可以移动到任何位置,比如房屋以东n+1米,房屋里面,房屋西侧……"}},{"title":"输入","value":{"format":"MD","content":"输入包含多组测试样例。第一行包含数字 `T` 代表测试样例数。\n\n对于每组测试样例,第一行包含两个数字 `n, m` (2 ≤ n ≤ 10\u003csup\u003e5\u003c/sup\u003e, 0 ≤ n ≤ 10\u003csup\u003e12\u003c/sup\u003e),表示植物的数量和机器人最大可以行走的步数。\n\n第二行包含 `n` 个数字 a\u003csub\u003e1\u003c/sub\u003e, a\u003csub\u003e2\u003c/sub\u003e, ... , a\u003csub\u003en\u003c/sub\u003e,其中 a\u003csub\u003ei\u003c/sub\u003e 表示第 `i` 棵植物的生长速度。\n\n保证测试样例中 `n` 的求和不超过 10\u003csup\u003e6\u003c/sup\u003e。"}},{"title":"输出","value":{"format":"MD","content":"对于每个测试样例,输出一行包含一个数字,表示可以达到的最大防御值。"}},{"title":"样例输入","value":{"format":"MD","content":"```\n2\n4 8\n3 2 6 6\n3 9\n10 10 1\n```"}},{"title":"样例输出","value":{"format":"MD","content":"```\n6\n4\n```"}},{"title":"提示","value":{"format":"MD","content":"在接下来的解释中,`E` 表示机器人向东移动1格,`W` 表示机器人向西移动1格。\n\n在第一组样例中,一个可行的方案是 `{E, E, W, E, E, W, E, E}`,这样我们可以达到 `d \u003d {6, 6, 12, 6}`。\n\n在第二组样例中,一个可行的方案是 `{E, E, E, E, W, E, W, E, W}`,这样我们可以达到 `d \u003d {10, 10, 4}`。"}}]}