两种字符，两种颜色

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定一个只含字符 0 和 1 的字符串 $s$。你需要把每个字符染成红色或蓝色。

若第 $i$ 个字符染成红色，你会获得 $r_i$ 枚金币；若染成蓝色，你会获得 $b_i$ 枚金币。

染色结束后，删除所有蓝色字符。在剩余字符串中，每个逆序对（左侧字符为 1、右侧字符为 0）会使你支付 $1$ 枚金币。

求最终最多能获得多少枚金币。

输入格式

第一行一个整数 $t$，表示测试用例数。

每个测试用例包含四行：

• 第一行一个整数 $n$；
• 第二行一个长度为 $n$ 的 01 字符串 $s$；
• 第三行 $n$ 个整数 $r_1,r_2,\ldots,r_n$；
• 第四行 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

输出格式

对每个测试用例输出一行一个整数，表示最大金币数。

样例输入

4
7
0100010
6 6 6 7 7 6 6
3 3 5 4 7 6 7
5
10111
9 8 5 7 5
4 4 7 8 4
10
0100000000
7 7 6 5 2 2 5 3 8 3
8 6 9 6 6 8 9 7 7 9
8
01010000
8 7 7 7 8 7 7 8
4 4 4 2 1 4 4 4

样例输出

43
36
76
52

数据范围

对于全部数据，$1\le t\le 10^4$，$1\le n$，$1\le r_i,b_i\le 10^{12}$，且单个输入文件中所有测试用例的 $n$ 之和不超过 $4\times10^5$。

每个测试点独立计分。