Problem 1203. -- One Stroke

## 1203: One Stroke

Time Limit: 2 Sec  Memory Limit: 1280 MB
Submit: 285  Solved: 65
[Submit][Status][Web Board]

## Description

There is a complete binary tree which includes n nodes. Each node on the tree has a weight w, each edge on the tree is directed from the parent node to the child node. Give you a pen, draw from the any node along the directed edge at one stroke. It is required that the sum of those drawn nodes’ s weight is no more than k. How many node can be drawn at most in one stroke?

## Input

The first line input an positive integer T(1<=T<=10)indicates the number of test cases. Next, each case occupies two lines. The first line input two positive integers n(1<=n<=10^6) and k,(1<=k<=10^9)

The second line input n integers w(1<=w <=10^3),, indicate the weight of nodes from the first level of the tree and from left to right.

## Output

For each test cases, output one line with the most number of nodes can be drawn in one stroke. If any node likes this doesn’t exists, output -1.

## Sample Input

1
5 6
2 3 4 1 7


## Sample Output

3


[Submit][Status]