G1. Последовательное сложение (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное различие между двумя версиями в том, что в этой версии ограничения ниже.

Изначально массив $$$a$$$ содержит только число $$$1$$$. Вы можете выполнить несколько операций, чтобы изменить массив. За одну операцию можно выбрать некоторую подпоследовательность $$$^{\dagger}$$$ из $$$a$$$ и вставить на любую позицию в $$$a$$$ элемент, равный сумме всех элементов подпоследовательности.

Вам дан массив $$$c$$$. Проверьте, можно ли получить из массива $$$a$$$ массив $$$c$$$, выполнив некоторое количество (возможно, 0) операций над исходным массивом.

$$$^{\dagger}$$$ Последовательность $$$b$$$ является подпоследовательностью последовательности $$$a$$$, если $$$b$$$ может быть получена из $$$a$$$ удалением нескольких (возможно, нуля, но не всех) элементов. Другими словами, операция выглядит так: выберем $$$k$$$ ($$$1 \leq k \leq |a|$$$) различных индексов $$$i_1, i_2, \dots, i_k$$$ и вставим в любое место $$$a$$$ новый элемент со значением, равным $$$a_{i_1} + a_{i_2} + \dots + a_{i_k}$$$.

Входные данные

Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 5000$$$) — длину массива $$$c$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ разделенных пробелами целых чисел $$$c_i$$$ ($$$1 \leq c_i \leq 5000$$$) — массив $$$c$$$, который вам нужно получить из массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$5000$$$.

Выходные данные

Для каждого набора входных данных выведите «YES» (без кавычек), если такая последовательность операций существует, и «NO» (без кавычек) в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
6
1
1
1
2
5
5 1 3 2 1
5
7 1 5 2 1
3
1 1 1
5
1 1 4 2 1
Выходные данные
YES
NO
YES
NO
YES
YES
Примечание

Для первого набора входных данных исходный массив $$$a$$$ уже равен $$$[1]$$$, поэтому ответ «YES».

Для второго набора входных данных после выполнения любого количества операций длина массива $$$a$$$ станет хотя бы два, а в начальном массиве элемента $$$2$$$ нет, поэтому получить массив $$$[2]$$$ невозможно, и ответ будет «NO».

Для третьего набора входных данных мы можем выполнить следующие операции, чтобы получить массив $$$c$$$:

  • Первоначально, $$$a = [1]$$$.
  • Выбрав подпоследовательность $$$[1]$$$ и вставив $$$1$$$ в массив, $$$a$$$ станет равным $$$[1, 1]$$$.
  • Выбрав подпоследовательность $$$[1, 1]$$$ и вставив $$$1+1=2$$$ в середину массива, $$$a$$$ станет равным $$$[1, 2, 1]$$$.
  • Выбрав подпоследовательность $$$[1, 2]$$$ и вставив $$$1+2=3$$$ после первой $$$1$$$ массива, $$$a$$$ станет равным $$$[1, 3, 2, 1]$$$.
  • Выбрав подпоследовательность $$$[1, 3, 1]$$$ и вставив $$$1+3+1=5$$$ в начало массива, $$$a$$$ станет равным $$$[5, 1, 3, 2, 1]$$$ (именно такой массив нам нужно было получить).