## 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 $$N$$ types of coins with various denominations. They would like to know if there is some combination of coins that sum up to the value $$S$$.

#### Input Specification

The first line will contain two integers $$N, S\ (1 \le N \le 100, 1 \le S \le 10\ 000)$$.

The second line will contain $$N$$ integers, $$c_1, c_2, \ldots, c_N\ (1 \le c_i \le 1\ 000)$$ 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 $$S$$, or NO otherwise.

#### Sample Input 1

3 6
1 4 5

#### Sample Output 1

YES

#### Explanation for Sample 1

We can use $$6$$ coins of value $$1$$ to make the sum of $$S = 6$$. 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 $$S = 11$$ with coins of value $$3$$ and $$7$$.

#### Sample Input 3

2 7
3 2

#### Sample Output 3

YES

#### Explanation for Sample 3

We can use $$1$$ coin of value $$3$$ and $$2$$ coins of value $$2$$ to make a total sum of $$7$$.