Subsequence Sum Existence

You are given an array of n non-negative integers and a target sum k. Your task is to determine whether there exists a subsequence of the array whose elements sum up exactly to k. A subsequence can be obtained by deleting some or no elements without changing the order of the remaining elements.

Dynamic Programming Approach:

Let \(dp[i]\) be a boolean value which indicates whether a sum of \(i\) can be formed using some elements of the array. Initially, \(dp[0]=true\) because a sum of 0 can always be achieved with an empty subsequence. For each number in the array, update the dp array backwards (from \(k\) down to the number). If \(dp[j-num]\) is true, then update \(dp[j]\) to true.

If \(dp[k]\) is true after processing the entire array, then output YES; otherwise, output NO.

inputFormat

The first line contains an integer T denoting the number of queries. For each query, the input is provided in the following three lines:

1. The first line contains an integer n, the number of elements in the array.
2. The second line contains n space-separated integers representing the array.
3. The third line contains an integer k, the target sum.

outputFormat

For each query, output a single line containing either YES if a subsequence with a sum exactly equal to k exists, or NO otherwise.

## sample

2
4
1 2 3 4
5
5
3 1 4 2 3
7

YES
YES

</p>