
155  The 2018 ACMICPC Asia Qingdao Regional Contest (Mirror)  E
BaoBao and DreamGrid are playing the game Plants vs. Zombies. In the game, DreamGrid grows plants to defend his garden against BaoBao's zombies. Plants vs. Zombies(?) (Image from pixiv. ID: 21790160; Artist: socha) There are $n$ plants in DreamGrid's 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's house. The $i$th plant has a defense value of $d_i$ and a growth speed of $a_i$. Initially, $d_i = 0$ for all $1 \le i \le n$. DreamGrid 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's 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. The defense value of the garden is defined as $\min\{d_i  1 \le i \le n\}$. DreamGrid needs your help to maximize the garden's defense value and win the game. Please note that:
InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The 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. The 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. It's guaranteed that the sum of $n$ in all test cases will not exceed $10^6$. OutputFor each test case output one line containing one integer, indicating the maximum defense value of the garden DreamGrid can get. Sample Input2 4 8 3 2 6 6 3 9 10 10 1 Sample Output6 4 HintIn the explanation below, 'E' indicates that the robot moves exactly 1 meter to the east from his current position, and 'W' indicates that the robot moves exactly 1 meter to the west from his current position. For the first test case, a candidate direction sequence is {E, E, W, E, E, W, E, E}, so that we have $d = \{6,6,12,6\}$ after the watering. For the second test case, a candidate direction sequence is {E, E, E, E, W, E, W, E, W}, so that we have $d = \{10, 10, 4\}$ after the watering. 