Обратите внимание на необычное ограничение по памяти.
Чеширский Кот задал Алисе загадку: даны \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) и цель \(m\), существует ли способ вставить \(+\) и \(\times\) в круги выражения \(\)a_1 \circ a_2 \circ \cdots \circ a_n = m\(\) так, чтобы оно стало истинным? Мы следуем обычному порядку операций: \(\times\) выполняется перед \(+\).
Алиса отлично играет в шахматы, но она не сильна в математике. Пожалуйста, помогите ей найти выход из Страны Чудес!
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если возможно достичь цель, вставив \(+\) или \(\times\), и «NO» в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
Возможные решения для первых четырех наборов входных данных приведены ниже. \(\)\begin{align*} 2 \times 1 + 1 \times 1 \times 2 &= 4 \\ 2 \times 1 + 1 + 1 \times 2 &= 5 \\ 2 \times 1 + 1 + 1 + 2 &= 6 \\ 2 + 1 + 1 + 1 + 2 &= 7 \\ \end{align*}\(\) В пятом наборе входных данных невозможно получить \(8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5 4
2 1 1 1 2
5 5
2 1 1 1 2
5 6
2 1 1 1 2
5 7
2 1 1 1 2
5 8
2 1 1 1 2
5 6
2 0 2 2 3
|
YES
YES
YES
YES
NO
YES
|