Find Sequence

Time Limit: 5000/3000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

Give you an positive integer sequence $a_1, a_2, \ldots, a_i, \ldots, a_n$, and they satisfy $a_1+a_2+ \ldots +a_i+ \ldots +a_n = M(0<M \leq 2^{22})$.
We can find new sequence $b_1=a_{id_1}, b_2=a_{id_2}, \ldots, b_x=a_{id_x}, \ldots, b_y=a_{id_y}, \ldots, b_t =a_{id_t}$, where if x != y then $id_x != id_y$. and this sequence satisfy:
(1) $b_1 \leq b_2 \leq \ldots \leq b_t$
(2) $b_2-b_1 \leq b_3-b_2 \leq \dots \leq b_t-b_{t-1}$
We can find many sequences $b_1, b_2, b_3, \ldots, b_t$. But we only want to know maximum t.

Input

The first line in the input file is an Integer $T(1 \leq T \leq 30)$.
The first line of each test case contains two integer $n, M(0<M \leq 2^{22})$.
Then a line have n integer, they represent $a_1, a_2, \ldots, a_i, \ldots, a_n$.

Output

For each test case, output the maximum t.

Sample Input

2 6 19 3 2 1 3 4 6 1 4194304 4194304

Sample Output

5 1
Hint
For the first testcase, The Sequence is 1 2 3 4 6

Hint

heyang

Source

BestCoder Round #13

提交代码