BaoBao 和 DreamGrid 正在玩《植物大战僵尸》游戏。在游戏中，DreamGrid 种植植物来保卫他的花园，抵御 BaoBao 的僵尸。

植物大战僵尸（？）

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 \mid 1 \le i \le n\}$。DreamGrid 需要你的帮助来最大化花园的防御值并赢得游戏。

请注意： 每次机器人必须先移动，然后才能给植物浇水； 机器人可以向东移动超过 $n$ 米远离房子，也可以回到房子，甚至可以移动到房子以西的位置。

输入格式

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

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

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

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

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

样例

输入格式 1

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

输出格式 1

6
4

说明

在下面的解释中，‘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\}$。