Subset Sum Knapsack

You are given a target weight m and a list of weights. Your task is to determine whether there exists a subset of the weights that sums up exactly to m. This is a classic subset-sum problem that can be solved using dynamic programming.

The problem can be formulated as follows: [ \text{Find a subset } S \subseteq {w_1, w_2, \ldots, w_n} \text{ such that } \sum_{w \in S} w = m. ] If such a subset exists, print YES; otherwise, print NO.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains an integer m (0 \(\leq m \leq 10^5\)) representing the target knapsack weight.
• The second line contains space-separated integers representing the weights of the items. There will be at least one weight and at most 100 weights.

outputFormat

Output a single line to standard output (stdout) containing either YES if there exists a subset of the given weights that exactly sums to m, or NO otherwise.## sample

9
3 34 4 12 5

YES