Minimum Boxes to Fulfill an Order

You are given a list of boxes, where each box contains a specific number of widgets. Your task is to choose the minimum number of boxes such that the total number of widgets exactly equals a given target \(W\). If it is impossible to reach exactly \(W\) widgets with the available boxes, output -1.

This problem is a variant of the subset sum problem with a twist: you must minimize the number of boxes used. An efficient approach to solving this problem is to use dynamic programming.

inputFormat

The first line of input contains two integers \(N\) and \(W\), where \(N\) is the number of boxes and \(W\) is the required total number of widgets.

The second line contains \(N\) integers. The \(i\)-th integer represents the number of widgets in the \(i\)-th box.

outputFormat

Print a single integer representing the minimum number of boxes required to exactly achieve \(W\) widgets. If it is impossible, print -1.

5 8
4 1 3 2 5

2