题目背景

原题链接：https://oier.team/problems/X11E。

---

「お願い　きみが欲しいの」

「頼り散らしてシックラブ　なんて最高ね」

「分けてくれなきゃ　君の“痛い”感じていたい」

「ねえいいでしょう？　吸い取って　救いたいんだってば」

题目描述

定义一个不可重集二元组 $(A,B)$ 是好的当且仅当能通过以下操作在有限次操作内将 $A$ 变成 $B$。

• 每次可以选择 $A$ 中一个数 $x$，将 $x$ 从 $A$ 中删除，再把 $x-1,x+1$ 加到 $A$ 中，若有相同只保留一个。

给定 $A,B$ 集合初始的值域 $[1,n]$，且都为整数，操作过程中可以超出 $[1,n]$。再给出 $B$ 集合，和一个长度为 $n$ 的数组 $p$。

求一个符合要求的 $A$，使得 $(A,B)$ 是好的，且满足 $\sum\limits_{i=1}^n [i \in A] \times p_i$ 最小。

输入格式

本题有多组测试数据。输入的第一行两个整数 $c,T$，分别表示子任务编号和测试数据组数，接下来输入每组测试数据。样例满足 $c=0$。

对于每组测试数据：

• 第一行，一个整数 $n$，表示集合 $A,B$ 初始值域。
• 第二行，一个长度为 $n$ 的 $01$ 字符串 $s_1 s_2 \cdots s_n$，其中若 $s_i=1$ 则表示 $i \in B$，否则表示 $i \notin B$。
• 第三行，$n$ 个整数 $p_1,p_2,\ldots,p_n$。

输出格式

对于每组测试数据，输出一行一个整数表示最小的答案。

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

提示

【样例解释 #1】

对于第一组测试数据，$A=\{ 1,4,5,8,9\}$ 为一个合法的答案。花费为 $3+(-3)+4+(-3)+(-5)=-4$。

对于第二组测试数据，$A=\{ 2,7\}$ 为一个合法的答案，因为可以通过分别操作 $2,7$ 变为 $\{1,3,6,8\}$，即集合 $B$。花费为 $0+2=2$。

【数据范围】

本题使用子任务捆绑。

对于所有测试数据，$1 \le T \le 10$，$1 \le n \le 10^5$，$-10^9 \le p_i \le 10^9$。

子任务编号	$n\le$	特殊性质	分值
$1$	$18$	无	$10$
$2$	$10^5$	A
$3$		B	$20$
$4$		C
$5$		无	$40$

• 特殊性质 A：保证 $B$ 集合大小不超过 $10$。
• 特殊性质 B：保证字符串 $s$ 中不会出现子串 101。
• 特殊性质 C：保证所有 $p_i$ 相等。