Problem Description

Xiao Lan is buying melons at a melon stall. There are $n$ melons in total, and the weight of the $i$-th melon is $A_i$. Xiao Lan is very skilled with a knife: he can split any melon into two exactly equal halves, but each melon can only be cut once.

Xiao Lan wants the total weight of the melons he buys to be exactly $m$.

Please output the minimum number of melons Xiao Lan needs to cut to obtain melons with total weight exactly $m$. If no matter what he does he cannot obtain melons with total weight exactly $m$, output $-1$.

Input Format

The first line contains two integers $n, m$, separated by a space, representing the number of melons and the total weight Xiao Lan wants to buy.

The second line contains $n$ integers $A_i$, separated by spaces, representing the weight of each melon.

Output Format

Output one line containing one integer, the answer.

3 10
1 3 13

2

Hint

Constraints

For $20\%$ of the testdata, $n \leq 10$.

For $60\%$ of the testdata, $n \leq 20$.

For all testdata, $1 \leq n \leq 30$, $1 \leq A_i \leq 10^9$, $1 \leq m \leq 10^9$.

Translated by ChatGPT 5