Subset Sum Problem: Taco

You are given a set of N integers and a target integer T. Your task is to determine whether there exists a subset of the provided integers that sums exactly to T. This is a classic dynamic programming problem often known as the Subset Sum Problem.

The problem can be formally stated as follows:

Given an integer \( N \), an array \( A = [a_1, a_2, \ldots, a_N] \) and a target integer \( T \), determine if there exists a subset of \( A \) whose elements sum to \( T \). Output "YES" if such a subset exists and "NO" otherwise.

Input and Output

• The input is provided via standard input (STDIN).
• The output should be printed via standard output (STDOUT).

Example

Input:
5
3 34 4 12 5
9

Output:
YES

Note: When \( N = 0 \), the only valid target is \( T = 0 \) (an empty set sums to 0).

inputFormat

The first line contains an integer ( N ) representing the number of integers.\nThe second line contains ( N ) space-separated integers.\nThe third line contains the target integer ( T ).

outputFormat

Print "YES" if there exists a subset of the given array whose sum equals ( T ), otherwise print "NO".## sample

5
3 34 4 12 5
9

YES