Minimum Number of Bricks Required

You are given a set of n different types of bricks, each with a certain length. Your task is to determine the minimum number of bricks required to construct a wall of exact length L. If it is not possible to build such a wall using the provided types of bricks, output -1.

You can solve this problem using a dynamic programming approach. Define an array \(dp[0\ldots L]\) where \(dp[i]\) represents the minimum number of bricks needed to achieve a total length of \(i\). The recurrence relation is given by:

\(dp[i] = \min_{b \in \text{brick_lengths} \text{ and } i \geq b}(dp[i-b] + 1)\)

with the base condition \(dp[0] = 0\). Your goal is to compute \(dp[L]\). If \(dp[L]\) remains infinite (or a very large number used to denote infinity), then it is impossible to construct the wall, and you should output -1.

inputFormat

The input is given in two lines:

• The first line contains two integers n and L separated by a space, where n is the number of brick types and L is the desired length of the wall.
• The second line contains n space-separated integers, representing the lengths of the bricks available.

outputFormat

Output a single integer representing the minimum number of bricks required to build a wall of length L. If it is not possible, output -1.

## sample

5 11
1 2 3 4 5

3

</p>