Migrated from Lutece 522 兰斯的后宫计划

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

总之兰斯想要在有限的经费之内圈出更多的领土。

兰斯所在那个世界是一条狭长的峡谷，可以近似为一条线段。戴眼镜的兰斯已经把世界分成了 $n$ 个小块，算好了攻略每块领土所需的经费（负数表示可以倒赚经费），并且为了更好地统治领土和之后选秀运动的便利，兰斯决定把领土弄成连续的。你需要去计算出兰斯最多能圈多少地！

Input

第一行一个整数$T$，表示数据的组数。

每组数据的第一行包含两个整数$n$($0<n\leq 100000$),$m$($0\leq m<10000$)，表示世界被兰斯分成$n$块以及兰斯的经费。

接下来一行，包含$n$个整数$a_1,a_2,\cdots ,a_n$($-10000<a_i<10000$)，表示攻略每块地所需经费。

数据量很大，请用scanf代替cin进行输入。

Output

对于每组数据，只输出一行。在一行中输出一个整数$n$，表示兰斯最多能圈的领土。

Samples

4
5 6
100 100 1 2 3
5 0
1 1 -4 1 1
5 0
1 2 3 4 5
5 50
1 1 100 1 1

3
5
0
2

Note

警告：建立国家，非专业人士，切勿模仿。

请勿尝试使用两重及以上(从$1$到$n$,或者从$i$到$n$)的循环来解决该题。否则会得到TLE的结果。

(什么是TLE?就是你的程序太慢啦，兰斯可没耐心等你那破程序跑个十天半个月的……)

也就是说，类似于这样的代码是不行的：

for(int i=0;i<n;i++)
    for(int j=i;j<n;j++)
        ...

Resources

兰斯系列@戴眼镜的兰斯