该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个二进制字符串 $s$，长度为 $n$，仅包含字符 $\texttt{0}$ 和 $\texttt{1}$，以及一个长度为 $n$ 的正整数数组 $\{c_1,c_2,\dots,c_n\}$，其中 $c_i$ 表示在位置 $i$ 发起一次后缀翻转操作的代价，其中，在位置 $i$ 发起的一次后缀翻转操作指：

$∙$ 对 $s_i,s_{i+1},\dots,s_n$ 中的每个字符进行 反置 操作，即将 $\texttt{0}$ 变为 $\texttt{1}$，$\texttt{1}$ 变为 $\texttt{0}$；

请计算使得字符串单调不降（即所有 $\texttt{0}$ 均在所有 $\texttt{1}$ 之前）所需的最小总代价。保证对于每个测试用例至少存在一种可行方案。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ 代表数据组数，对于每组测试数据：

第一行输入一个整数 $n$，表示字符串长度。

第二行输入一个长度为 $n$、由字符 $\texttt{0}$ 和 $\texttt{1}$ 构成的字符串 $s$。

第三行输入 $n$ 个整数 $c_1,c_2,\dots,c_n$，第 $i$ 个整数 $c_i$ 表示在位置 $i$ 发起一次后缀翻转操作的代价。

输出格式

对于每组测试数据，新起一行输出一个整数，表示使字符串单调不降的最小总代价。

2
3
010
2 1 3
3
001
5 5 5

1
0

样例解释

对于第一组测试数据，最优操作是在位置 $2$ 处进行一次后缀翻转，代价 $1$。

对于第二组测试数据，字符串 $s=\texttt{"001"}$ 已经是单调不降的，无需进行任何操作，总代价 $0$。

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 50,1 \leq n,\sum n \leq 2 \times 10^{5},s_i \in \{0,1\},1 \leq c_i \leq 10^9(1 \leq i \leq n)$。