You are given $$$N$$$ positive integers and a target sum $$$S$$$. You can choose any subset of the $$$N$$$ integers (each at most once). Your task is to determine whether there exists a subset whose sum is exactly $$$S$$$.
Output YES if such a subset exists, otherwise output NO.
The first line contains two integers $$$N$$$ and $$$S$$$ ($$$1 \le N \le 300$$$, $$$1 \le S \le 5000$$$) — the number of elements and the target sum.
The second line contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$1 \le a_i \le 5000$$$) — the elements of the array.
Print YES if it is possible to reach the sum $$$S$$$ using a subset of the given numbers, otherwise print NO.
Input:
4 6 3 2 4 1
Output:
YES
Input:
3 5 2 2 2
Output:
NO
In the first example, selecting $$$2$$$ and $$$4$$$ gives a total sum of $$$6$$$.
In the second example, no subset sums to exactly $$$5$$$.