Description

A set pair $(A, B)$ is defined as "good" if and only if $A$ can be transformed into $B$ through a finite number of the following operations:

• Choose a number $x$ from $A$, remove $x$ from $A$, then add $x-1$ and $x+1$ to $A$. If duplicates exist, only one copy is retained.

Given that the initial value ranges of sets $A$ and $B$ are $[1, n]$ (containing integers), operations may produce values outside $[1, n]$. Additionally, you are given the set $B$ and a length-$n$ array $p$.

Find a valid $A$ such that $(A, B)$ is good, and minimize the sum $\sum\limits_{i=1}^n [i \in A] \times p_i$.

Input Format

Multiple test cases.
The first line contains two integers $c$ and $T$, representing the subtask number and the number of test cases, respectively. Subsequent lines contain the test data. Sample inputs satisfy $c=0$.

For each test case:

• The first line contains an integer $n$, the initial value range of sets $A$ and $B$.
• The second line contains a length-$n$ binary string $s_1 s_2 \cdots s_n$, where $s_i = 1$ indicates $i \in B$, and $s_i = 0$ indicates $i \notin B$.
• The third line contains $n$ integers $p_1, p_2, \ldots, p_n$.

Output Format

For each test case, output a single integer representing the minimal possible sum.

0 2
9
100110011
3 0 -1 -3 4 -1 -4 -3 -5
8
10100101
2 0 2 4 1 1 2 2

-4
2

Hint

Explanation #1

For the first test case, $A = \{1, 4, 5, 8, 9\}$ is a valid solution. The cost is $3 + (-3) + 4 + (-3) + (-5) = -4$.

For the second test case, $A = \{2, 7\}$ is valid. Operating on $2$ and $7$ transforms $A$ into $\{1, 3, 6, 8\}$, which matches $B$. The cost is $0 + 2 = 2$.

Constraints

For all test data: $1 \le T \le 10$, $1 \le n \le 10^5$, $-10^9 \le p_i \le 10^9$.

• Special Property A: The size of set $B$ does not exceed 10.
• Special Property B: The binary string $s$ contains no substring 101.
• Special Property C: All $p_i$ are equal.

Translated by DeepSeek R1