Minimum Number of Umbrellas

Given a target of N people and a collection of umbrellas with varying capacities, determine the smallest number of umbrellas whose combined coverage is exactly N people.

Input

• N ($1 \le N \le 10000$): The number of people that must be covered.
• umbrellas (List[int], 1 ≤ length ≤ 10000): A list of umbrella coverage amounts.

Output

Return the minimum number of umbrellas required to cover exactly N people. If no exact combination exists, return -1.

Example

Example 1

Input: N = 5, umbrellas = [3, 3, 1, 2]
Output: 2

Two umbrellas with capacities 3 and 2 provide coverage for exactly 5 people.

Example 2

Input: N = 7, umbrellas = [2, 3, 4]
Output: 2

The umbrellas covering 3 and 4 people combine to cover exactly 7 people.

Additional Requirements

• The function should return -1 when no valid exact coverage can be formed.
• The approach should be efficient enough for large input sizes.

Example

Input:
5
3 3 1 2

Output: 2

Two umbrellas with capacities 3 and 2 provide coverage for exactly 5 people.