Exact Coin Payment

You are given an integer T representing the number of test cases. In each test case, you are provided with:

• An integer n which denotes the number of available coin denominations.
• An array of n coin denominations.
• An integer k representing the target amount you need to pay.

You have an unlimited supply of each coin. Your task is to determine whether it is possible to pay exactly k using the coins available. In other words, you need to check if there exists a combination of the coins (repetitions allowed) that sums up to k.

This problem can be solved using dynamic programming. Define a boolean array \(dp[0 \ldots k]\) where \(dp[i]\) is true if and only if there exists a sequence of coins that sums to \(i\). The recurrence used is:

$$dp[i] = \bigvee_{coin \in coins,\, i \geq coin} dp[i-coin] $$

with the base condition (dp[0] = true). Output YES if (dp[k]) is true, otherwise output NO.

inputFormat

The input is read from stdin and has the following format:

T
n
c1 c2 ... cn
k
... (repeats for T test cases)

Where:

• T is the number of test cases (1 ≤ T ≤ 100).
• For each test case, the first line contains an integer n (1 ≤ n ≤ 100) — the number of coin denominations.
• The next line contains n space-separated integers denoting the coin denominations.
• The third line contains an integer k (0 ≤ k ≤ 10,000) — the target amount.

outputFormat

For each test case, output a single line to stdout containing YES if the exact amount k can be paid using the coins, otherwise output NO.

## sample

3
3
1 2 3
5
2
2 4
7
2
3 6
9

YES
NO
YES

</p>