A post office sells stamps in k distinct denominations, with an unlimited supply of each. Find the minimum number of stamps whose values sum to EXACTLY a target postage T. If it is impossible to make exactly T, print -1.
Input format
Line 1: two integers T k.
Line 2: k distinct space-separated positive integers, the stamp denominations.
Output format
A single integer: the minimum number of stamps summing to exactly T, or -1 if impossible. (If T = 0, the answer is 0.)
Constraints
- 0 ≤ T ≤ 3000
- 1 ≤ k ≤ 6
- 1 ≤ each denomination ≤ 500