The 2018 ICPC Asia Qingdao Regional Programming Contest (The 1st Universal Cup, Stage 9: Qingdao) |
---|
Finished |
BaoBao and DreamGrid are playing the game Plants vs. Zombies. In the game, DreamGrid grows plants to defend his garden against BaoBao's zombies.
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:
There 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, ... , 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$$$.
For each test case output one line containing one integer, indicating the maximum defense value of the garden DreamGrid can get.
2
4 8
3 2 6 6
3 9
10 10 1
6
4
In 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.
Name |
---|