Time Limit: 1s
Memory Limit: 65535k
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?
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 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.
80% test cases: 1 <= n <= 10^3
For 100% test cases: 1 <= n <= 10^6
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.