### Problem Statement

Christmas is coming soon and you still have so many things to buy. You are going to the store and don't expect to spend more than X dollars. You want to be able to pay any integer amount not exceeding X dollars, and you want to take as few coins as possible to achieve this.

You are given a int[] values, each element of which describes the dollar value of a kind of coin. You have an unlimited supply of each kind of coin. Return the minimal number of coins you need to take, or -1 if it is impossible to achieve your goal.

### Definition

 Class: Shopping Method: minNumber Parameters: int, int[] Returns: int Method signature: int minNumber(int X, int[] values) (be sure your method is public)

### Constraints

-X will be between 1 and 1000, inclusive.
-values will contain between 1 and 10 elements, inclusive.
-Each element of values will be between 1 and 1000, inclusive.
-The elements in values will be distinct.

### Examples

0)

 `20` `{1, 2, 5, 10}`
`Returns: 5`
 Taking 5 coins with values {1,2,2,5,10} allows you to pay any integer amount between 1 and 20, inclusive.
1)

 `7` `{2, 4, 1, 7}`
`Returns: 3`
 Here, taking {2,4,1} is enough.
2)

 `20` `{2,4,6,8}`
`Returns: -1`
 These nominals allow you to pay only even amounts.
3)

 `600` `{1,2,3,10,11,30}`
`Returns: 25`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6479

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10011&pm=6479

slex

#### Testers:

PabloGilberto , brett1479 , Olexiy , marian

Greedy