Minimum Battery Recharges

A robotics company seeks to optimize the battery usage of its robots by minimizing the number of battery recharges needed to cover a given distance. You are provided with a set of battery types where each battery's capacity is the maximum distance it can travel. A robot can use a battery until its maximum range is reached, then it must be recharged, at which point it can switch to any available battery (each battery can only be used once).

Given an integer \(N\) representing the number of batteries, a target distance \(D\), and an array of \(N\) integers where the \(i^{th}\) integer denotes the maximum distance the \(i^{th}\) battery can cover, determine the minimum number of battery recharges required to cover the distance \(D\). If it is impossible to cover \(D\) with the available batteries, output \(-1\).

For example:

• Input: 5 70 and battery capacities: 10 20 30 40 50 → Output: 2
• Input: 4 15 and battery capacities: 4 3 7 5 → Output: 3
• Input: 3 10 and battery capacities: 1 2 3 → Output: -1

inputFormat

The input is given in two lines. The first line contains two space-separated integers \(N\) (the number of available batteries) and \(D\) (the required distance to cover). The second line contains \(N\) space-separated integers representing the capacities of the batteries.

For example:

5 70
10 20 30 40 50

outputFormat

Output a single integer representing the minimum number of battery recharges required to cover the distance \(D\). If it is impossible, output \(-1\).

## sample

5 70
10 20 30 40 50

2

</p>