CF2179E Blackslex and Girls

After failing to pick up a girl using De Bruijn sequence of fixed-length bitstrings, Blackslex has turned his attention towards politics. Due to his high charisma, he is now in charge of drawing borders for the $ n $ voting districts of his country. In Blackslex's country, there are $ x $ voters for party A and $ y $ voters for party B. Using his amazing drawing skills, he can allocate voters from any party into any district of his choice. His history with bitstrings has led him to wonder if he can allocate voters such that the winner of each district follows a certain bitstring pattern. To avoid suspicion, he must also allocate at least $ p_i $ voters into each district. Tell him if it is possible! Formally, you are given a binary string $ s $ of length $ n $ , an array $ p $ of length $ n $ , and two integers $ x $ and $ y $ . You want to determine whether there exist two arrays of nonnegative integers $ a $ and $ b $ of length $ n $ that satisfy the following conditions: - $ a_1 + a_2 + \dots + a_n = x $ - $ b_1 + b_2 + \dots + b_n = y $ - For every $ 1 \leq i \leq n $ , $ a_i + b_i \geq p_i $ - For every $ 1 \leq i \leq n $ : - If $ s_i = 0 $ then $ a_i > b_i $ - If $ s_i = 1 $ then $ b_i > a_i $

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The first line of each test case contains three integers $ n $ , $ x $ , and $ y $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ , $ 1 \leq x, y \leq 10^9 $ ). The second line contains a binary string $ s $ of length $ n $ . The third line contains $ n $ integers $ p_1, p_2, \dots, p_n $ ( $ 1 \leq p_i \leq 10^9 $ ). The sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, print (case-insensitive) YES if there exist arrays $ a, b $ satisfying all conditions, or NO otherwise.

In the first test case, one of the possible distributions of voters is: $ a = [2, 0, 3] $ and $ b = [0, 4, 1] $ . In the third test case, one of the possible distributions of voters is: $ a = [2, 2] $ and $ b = [1, 1] $ . For the other test cases, it can be shown that there are no distributions of voters that satisfy the conditions.