Minimizing Splits to Achieve Target Weight

You are given n melons, where the i-th melon weighs \(A_i\). Initially, if you buy a melon without modification, you must take the entire melon, obtaining a weight of \(A_i\). However, you have a special ability: you can split a melon exactly once into two equal halves. If you choose to split a melon, then you are only allowed to purchase one of its halves (of weight \(\frac{A_i}{2}\)); the other half is discarded. Splitting a melon incurs one operation.

Your goal is to purchase melons so that the total weight is exactly \(m\). In other words, for each melon you decide either to buy it whole (contributing \(A_i\)) or to split it and then buy only one half (contributing \(\frac{A_i}{2}\)). Let \(S=\sum_{i=1}^n A_i\) denote the total weight if you buy everything whole. Note that splitting the i-th melon reduces its contribution by \(\frac{A_i}{2}\). Hence, if you split a subset \(X\) of melons, the total weight becomes

[ S-\sum_{i\in X} \frac{A_i}{2},=,m. ]

This is equivalent to finding a subset \(X\) such that

[ \sum_{i\in X} \frac{A_i}{2} = S-m. ]

Multiplying both sides by 2 gives:

[ \sum_{i\in X} A_i = 2S - 2m. \quad (\star) ]

Your task is to choose a subset \(X\) with minimum size such that equation (\(\star\)) holds. If no such subset exists (or if \(S < m\)), output -1. If \(S\) is already equal to \(m\) then no split is needed and the answer is 0.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n \le N,\ m \ge 0)\) — the number of melons and the target total weight, respectively.

The second line contains \(n\) integers \(A_1, A_2, \ldots, A_n\) \((1 \le A_i \le M)\), where \(A_i\) denotes the weight of the \(i\)-th melon.

outputFormat

Output a single integer — the minimum number of melons that need to be split so that one can purchase pieces with total weight exactly \(m\). If it is impossible to achieve exactly \(m\), output -1.

sample

3 6
4 2 1

1