字符串min-18

题号：NC295907
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个二进制字符串 $s$ ，长度为 $n$ ，仅包含字符 $\texttt{`0'}$ 和 $\texttt{`1'}$ ，以及一个长度为 $n$ 的正整数数组 $\{c_1,c_2,\dots,c_n\}$ ，其中 $c_i$ 表示在位置 $i$ 发起一次后缀翻转操作的代价，其中，在位置 $i$ 发起的一次后缀翻转操作指：
$\hspace{23pt}\bullet\,$ 对 $s_i,s_{i+1},\dots,s_n$ 中的每个字符进行反置操作，即将 $\texttt{`0'}$ 变为 $\texttt{`1'}$ ， $\texttt{`1'}$ 变为 $\texttt{`0'}$ ；
$\hspace{15pt}$ 请计算使得字符串单调不降（即所有 $\texttt{`0'}$ 均在所有 $\texttt{`1'}$ 之前）所需的最小总代价。保证对于每个测试用例至少存在一种可行方案。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数 ，表示字符串长度。
第二行输入一个长度为 、由字符  和  构成的字符串 。
第三行输入  个整数 ，第  个整数  表示在位置  发起一次后缀翻转操作的代价。

输出描述:

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

示例1

输入

复制

输出

复制

1
0

说明

对于第一组测试数据，最优操作是在位置  处进行一次后缀翻转，代价 。
对于第二组测试数据，字符串  已经是单调不降的，无需进行任何操作，总代价 。