# [ICPC2018 Qingdao R] Plants vs. Zombies

## 题意翻译

给定 $n$ 个植物和 $m$ 的步数限制，每个植物在位置 $1\dots n$ 上。你初始时在位置 $0$，每次可以移动到相邻的位置上。
每次设你走完一步后到达的位置是 $i$，则会使得这个位置的植物的高度增加 $a_i$。设 $d_i$ 为走完 $m$ 步后位置 $i$ 的植物高度，求出一个最优的走法使得 $\min\limits_{1 \le i \le n} d_i$ 最大。
$2\leq n\leq 10 ^ 5$，$0\leq m\leq 10 ^ {12}$，$1\leq a_i\leq 10 ^ 5$，$\sum n\leq 10 ^ 6$。

## 题目描述

BaoBao and DreamGrid are playing the game $\textit{Plants vs. Zombies}$. In the game, DreamGrid grows plants to defend his garden against BaoBao's zombies.
![](https://cdn.luogu.com.cn/upload/image_hosting/9tyl9ix3.png)
$\textit{Plants vs. Zombies(?)} \\
\textit{(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.
- Each time the robot MUST move before watering a plant;
- It's 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.

## 输入输出格式

### 输入格式

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.

## 输入输出样例

### 输入样例 #1

```
2
4 8
3 2 6 6
3 9
10 10 1
```

### 输出样例 #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.