Sort

Recently, Bob has just learnt a naive sorting algorithm: merge sort. Now, Bob receives a task from Alice.
Alice will give Bob $N$ sorted sequences, and the $i$-th sequence includes $a_i$ elements. Bob need to merge all of these sequences. He can write a program, which can merge no more than $k$ sequences in one time. The cost of a merging operation is the sum of the length of these sequences. Unfortunately, Alice allows this program to use no more than $T$ cost. So Bob wants to know the smallest $k$ to make the program complete in time.

The first line of input contains an integer $t_0$, the number of test cases. $t_0$ test cases follow.
For each test case, the first line consists two integers $N~(2 \leq N \leq 100000)$ and $T~(\sum_{i=1}^{N}a_i < T < 2^{31}
)$.
In the next line there are $N$ integers $a_1, a_2, a_3, ... , a_N(\forall i, 0 \leq a_i \leq 1000)$.

For each test cases, output the smallest $k$.

1
5 25
1 2 3 4 5

3

2016 ACM/ICPC Asia Regional Qingdao Online