A Coin Problem

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type

Your parents have generously given you types of coins with various denominations. They would like to know if there is some combination of coins that sum up to the value .

Input Specification

The first line will contain two integers .

The second line will contain integers, the denominations of the coins that your parents will give you. Note that the same denomination of coin may be used multiple times.

Output Specification

Print YES if it is possible to use some combination of the coins to sum up to , or NO otherwise.

Sample Input 1

3 6
1 4 5

Sample Output 1

YES

Explanation for Sample 1

We can use coins of value to make the sum of . Note that there are other ways as well.

Sample Input 2

2 11
3 7

Sample Output 2

NO

Explanation for Sample 2

There are no ways to make with coins of value and .

Sample Input 3

2 7
3 2

Sample Output 3

YES

Explanation for Sample 3

We can use coin of value and coins of value to make a total sum of .