Description

BaoBao 和 DreamGrid 正在玩游戏《植物大战僵尸》。在游戏中，DreamGrid 种植植物来保护他的花园免受 BaoBao 的僵尸攻击。

《植物大战僵尸（？）》

（图片来自 pixiv。ID: 21790160；艺术家：socha）

DreamGrid 的花园里有 $n$ 株植物，按一条直线排列。从西到东，植物从 1 到 $n$ 编号，第 $i$ 株植物位于 DreamGrid 的房子东边 $i$ 米处。第 $i$ 株植物的防御值为 $d_i$，生长速度为 $a_i$。最初，所有 $1 \le i \le n$ 的 $d_i = 0$。

DreamGrid 使用一个机器人来浇灌植物。机器人最初在他的房子里。在一次浇水步骤中，DreamGrid 会选择一个方向（东或西），机器人沿该方向正好移动 1 米。移动后，如果第 $i$ 株植物位于机器人的位置，机器人将浇灌植物，并将 $a_i$ 加到 $d_i$ 上。由于机器人的水是有限的，最多可以进行 $m$ 步。

花园的防御值定义为 $\min\{d_i | 1 \le i \le n\}$。DreamGrid 需要你的帮助来最大化花园的防御值并赢得比赛。

• 每次机器人必须在浇灌植物之前移动；
• 机器人可以移动超过 $n$ 米到房子东边，或者移回房子，甚至移动到房子西边。

Input Format

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 10^5$, $0 \le m \le 10^{12}$)，表示植物的数量和机器人可以移动的最大步数。

第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($1 \le a_i \le 10^5$)，其中 $a_i$ 表示第 $i$ 株植物的生长速度。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

Output Format

对于每个测试用例输出一行，包含一个整数，表示 DreamGrid 可以获得的花园的最大防御值。

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

6
4

Hint

在下面的解释中，E 表示机器人从当前位置向东移动 1 米，W 表示机器人从当前位置向西移动 1 米。

对于第一个测试用例，一个候选方向序列是 $\{E, E, W, E, E, W, E, E\}$，这样我们有 $d = \{6,6,12,6\}$ 在浇水后。

对于第二个测试用例，一个候选方向序列是 $\{E, E, E, E, W, E, W, E, W\}$，这样我们有 $d = \{10, 10, 4\}$ 在浇水后。

题面翻译由 ChatGPT-4o 提供。