思路

用双指针维护当前仍在两端的船：左指针 $i$ 指向当前最左存活船，右指针 $j$ 指向当前最右存活船；并维护当前轮到“左端先打”还是“右端先打”的布尔量 $left$ （初始为“左端先打”，即 $left=\mathrm{true}$ ）。

设当前两端剩余耐久分别为 $L$ （即 $a_i$ 的剩余）与 $R$ （即 $a_j$ 的剩余）。从当前轮次开始，攻击顺序是严格左右交替，因此：

据此可以 一次性 计算让某一端被打沉所需的最少攻击次数：

题目内容

$n$ 艘船出发去探索海洋深处。这些船编号从 $1$ 到 $n$ ，按升序依次排列；第 $i$ 艘船的耐久度为 $a_i$ 。

海怪按特定顺序对这些船发动了 $k$ 次攻击。首先，它攻击第一艘船，然后是最后一艘，接着又攻击第一艘，依此类推。

海怪的每次攻击都会使船的耐久度降低 $1$ 。当船的耐久度降至 $0$ 时，它就会沉没，不再受到攻击(因此该船不再是第一艘或最后一艘，海怪只会攻击尚未沉没的船)。如果所有船都沉没了，海怪就没有可攻击的目标，便会游走。

例如，如果 $n=4，k=5$ ，且 $a=[1,2,4,3]$ ，将会发生以下情况：

海怪攻击第一艘船，其耐久度变为 $0$ ，现在 $a=[2,4,3]$ ;

海怪攻击最后一艘船，现在 $a=[2,4,2]$ ;

海怪攻击第一艘船，现在 $a=[1,4,2]$ ;

海怪攻击最后一艘船，现在 $a=[1,4,1]$ ;

海怪攻击第一艘船，其耐久度变为 $0$ ，现在 $a=[4,1]$ 。

请问海怪攻击后有多少艘船沉没了？

输入包括多组测试数据。

第一行包含一个整数 $t(1≤t≤10^4)$ 表示测试数据的组数。

对于每个测试用例：

第一行包含两个整数 $n$ 和 $k(1≤n≤2*10^5,1≤k≤10^{15})$ ，表示船的数量以及海怪攻击船的次数。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$ ，表示船的耐久度。

对于每个测试用例，在单独的一行中输出被海怪击沉的船的数量。

输入

输出