Sentence Weight Challenge

You are given an integer w and a list of sentences. Each sentence consists solely of the characters '+' and '-' and has an associated weight defined by the formula \( |\#(+) - \#(-)| \). Your task is to determine if it is possible to choose a subset (possibly empty) of these sentences such that the sum of their weights is exactly w.

Note: The weight of a sentence is computed by counting the number of '+' characters and the number of '-' characters, taking the difference, and then taking the absolute value. For instance, the sentence "+--" has a weight of \( |1 - 2| = 1 \).

If such a subset exists, output "YES"; otherwise, output "NO".

inputFormat

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

• The first line contains an integer \(w\) (\(0 \le w \le 10^9\)), the desired total weight.
• The second line contains an integer \(n\), the number of sentences.
• Each of the next \(n\) lines contains a non-empty string composed solely of the characters '+' and '-'.

outputFormat

Output a single line to standard output (stdout): "YES" if it is possible to select a subset of the sentences whose weights sum to \(w\), otherwise "NO".

2
3
++
+-
--

YES