{"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":"HTML","content":"\t\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n\t MathJax.Hub.Config({\n\t extensions: [\"tex2jax.js\"],\n\t jax: [\"input/TeX\", \"output/SVG\"],\n\t tex2jax: {\n\t inlineMath: [ [\u0027$\u0027,\u0027$\u0027], [\"\\\\(\",\"\\\\)\"] ],\n\t displayMath: [ [\u0027$$\u0027,\u0027$$\u0027], [\"\\\\[\",\"\\\\]\"] ],\n\t processEscapes: true\n\t },\n\t });\n\t\u003c/script\u003e\n\t\u003cscript type\u003d\"text/javascript\"\n\t src\u003d\"https://cdn.staticfile.org/mathjax/2.7.0/MathJax.js\"\u003e\n\t\u003c/script\u003e\n \u003cp\u003e题目翻译:有个机器人一开始在第0格,有n个格子,从1 - n左到右一列,然后你可以走m步,只能相邻的走,每踩到第i个格子该格子加ai点数字,一开始所有格子都是0,现在求走完m步以后,所有格子里最小的数字最大是多少?\n \u003cp\u003eBaoBao and DreamGrid are playing the game \u003ci\u003ePlants vs. Zombies\u003c/i\u003e. In the game, DreamGrid grows plants to defend his garden against BaoBao\u0027s zombies.\u003c/p\u003e \n \u003ccenter\u003e \n \u003cimg SRC\u003d\"CDN_BASE_URL/6a26e601c7668f5c681dbd8ca2cf6797?v\u003d1551441941\" width\u003d\"500px\"\u003e\n \u003cbr\u003e \n \u003ci\u003ePlants vs. Zombies(?)\u003cbr\u003e (Image from pixiv. ID: 21790160; Artist: socha)\u003c/i\u003e \n \u003c/center\u003e \n \u003cp\u003eThere are $n$ plants in DreamGrid\u0027s garden arranged in a line. From west to east, the plants are numbered from 1 to $n$ and the $i$-th plant lies $i$ meters to the east of DreamGrid\u0027s house. The $i$-th plant has a defense value of $d_i$ and a growth speed of $a_i$. Initially, $d_i \u003d 0$ for all $1 \\le i \\le n$.\u003c/p\u003e \n \u003cp\u003eDreamGrid uses a robot to water the plants. The robot is in his house initially. In one step of watering, DreamGrid will choose a direction (east or west) and the robot moves exactly 1 meter along the direction. After moving, if the $i$-th plant is at the robot\u0027s position, the robot will water the plant and $a_i$ will be added to $d_i$. Because the water in the robot is limited, at most $m$ steps can be done.\u003c/p\u003e \n \u003cp\u003eThe defense value of the garden is defined as $\\min\\{d_i | 1 \\le i \\le n\\}$. DreamGrid needs your help to maximize the garden\u0027s defense value and win the game.\u003c/p\u003e \n \u003cp\u003ePlease note that:\u003c/p\u003e \n \u003cul\u003e \n \u003cli\u003eEach time the robot MUST move before watering a plant;\u003c/li\u003e \n \u003cli\u003eIt\u0027s OK for the robot to move more than $n$ meters to the east away from the house, or move back into the house, or even move to the west of the house.\u003c/li\u003e \n \u003c/ul\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e \n \u003cp\u003eThe first line contains two integers $n$ and $m$ ($2 \\le n \\le 10^5$, $0 \\le m \\le 10^{12}$), indicating the number of plants and the maximum number of steps the robot can take.\u003c/p\u003e \n \u003cp\u003eThe second line contains $n$ integers $a_1, a_2, \\dots, a_n$ ($1 \\le a_i \\le 10^5$), where $a_i$ indicates the growth speed of the $i$-th plant.\u003c/p\u003e \n \u003cp\u003eIt\u0027s guaranteed that the sum of $n$ in all test cases will not exceed $10^6$.\u003c/p\u003e \n \u003ch4"}},{"title":"Output","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003eFor each test case output one line containing one integer, indicating the maximum defense value of the garden DreamGrid can get.\u003c/p\u003e \n \u003ch4"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cpre\u003e2\n4 8\n3 2 6 6\n3 9\n10 10 1\n\u003c/pre\u003e \n \u003ch4"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cpre\u003e6\n4\n\u003c/pre\u003e \n \u003ch4"}},{"title":"Hint","value":{"format":"HTML","content":"\u003c/h4\u003e \n \u003cp\u003eIn the explanation below, \u0027E\u0027 indicates that the robot moves exactly 1 meter to the east from his current position, and \u0027W\u0027 indicates that the robot moves exactly 1 meter to the west from his current position.\u003c/p\u003e \n \u003cp\u003eFor the first test case, a candidate direction sequence is {E, E, W, E, E, W, E, E}, so that we have $d \u003d \\{6,6,12,6\\}$ after the watering.\u003c/p\u003e \n \u003cp\u003eFor the second test case, a candidate direction sequence is {E, E, E, E, W, E, W, E, W}, so that we have $d \u003d \\{10, 10, 4\\}$ after the watering.\u003c/p\u003e \n "}}]}