E. Blackslex и девушки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После неудачной попытки познакомиться с девушкой, используя последовательность Де Бруйна фиксированной длины битовых строк, Blackslex обратил свое внимание на политику.

Из-за его высокой харизмы он теперь отвечает за проведение границ для $$$n$$$ избирательных округов своей страны. В стране Blackslex есть $$$x$$$ избирателей за партию A и $$$y$$$ избирателей за партию B. Используя свои удивительные навыки рисования, он может распределять избирателей из любой партии по любому округу по своему выбору.

Его история с битовыми строками заставила его задуматься, сможет ли он распределить избирателей так, чтобы победитель в каждом округе следовал определенному шаблону битовой строки. Чтобы избежать подозрений, он также должен распределить как минимум $$$p_i$$$ избирателей в каждый округ. Скажите ему, возможно ли это!

Формально, вам дана двоичная строка $$$s$$$ длиной $$$n$$$, массив $$$p$$$ длиной $$$n$$$ и два целых числа $$$x$$$ и $$$y$$$.

Вы хотите определить, существуют ли два массива неотрицательных целых чисел $$$a$$$ и $$$b$$$ длиной $$$n$$$, которые удовлетворяют следующим условиям:

  • $$$a_1 + a_2 + \dots + a_n = x$$$
  • $$$b_1 + b_2 + \dots + b_n = y$$$
  • Для каждого $$$1 \leq i \leq n$$$, $$$a_i + b_i \geq p_i$$$
  • Для каждого $$$1 \leq i \leq n$$$:
    • Если $$$s_i = 0$$$, то $$$a_i \gt b_i$$$
    • Если $$$s_i = 1$$$, то $$$b_i \gt a_i$$$
Входные данные

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

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$x$$$ и $$$y$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq x, y \leq 10^9$$$).

Вторая строка содержит двоичную строку $$$s$$$ длиной $$$n$$$.

Третья строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq 10^9$$$).

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите (без учета регистра) YES, если существуют массивы $$$a, b$$$, удовлетворяющие всем условиям, или NO в противном случае.

Пример
Входные данные
6
3 5 5
010
2 4 3
4 2 3
0001
1 1 1 1
2 4 2
00
3 3
4 23 20
1111
2 2 2 2
1 25 26
0
51
2 4 2
00
3 4
Выходные данные
YES
NO
YES
NO
NO
NO
Примечание

В первом наборе входных данных одно из возможных распределений избирателей: $$$a = [2, 0, 3]$$$ и $$$b = [0, 4, 1]$$$.

В третьем наборе входных данных одно из возможных распределений избирателей: $$$a = [2, 2]$$$ и $$$b = [1, 1]$$$.

Для остальных наборов входных данных можно показать, что нет распределений избирателей, которые удовлетворяют условиям.