题目描述

给定四个整数 $n$、$c_0$、$c_1$ 和 $h$，以及一个长度为 $n$ 的二进制字符串 $s$。

二进制字符串是仅由字符 $0$ 和 $1$ 组成的字符串。

你可以将字符串 $s$ 中的任意字符进行更改（更改后字符串仍需为二进制字符串）。每更改一个字符需要支付 $h$ 个硬币。

在进行若干次（也可以不进行）更改后，你需要购买整个字符串。购买字符串时，你需要购买其中的每一个字符。购买字符 $0$ 需要支付 $c_0$ 个硬币，购买字符 $1$ 需要支付 $c_1$ 个硬币。

请你计算，购买该字符串所需支付的最少硬币数。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10$），表示测试用例的数量。接下来的 $2t$ 行描述每个测试用例。

每个测试用例的第一行包含四个整数 $n$、$c_0$、$c_1$、$h$（$1 \leq n, c_0, c_1, h \leq 1000$）。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。

输出格式

对于每个测试用例，输出一个整数，表示购买该字符串所需支付的最少硬币数。

说明/提示

在第一个测试用例中，你可以直接购买所有字符并支付 $3$ 个硬币，因为字符 $0$ 和 $1$ 的价格都是 $1$ 个硬币。

在第二个测试用例中，你可以先将第 $2$ 个和第 $4$ 个字符从 $1$ 改为 $0$，为此支付 $2$ 个硬币。此时字符串变为 $00000$。然后你可以购买该字符串，支付 $5 \times 10 = 50$ 个硬币。总共需要支付 $2 + 50 = 52$ 个硬币。

由 ChatGPT 4.1 翻译

样例

6
3 1 1 1
100
5 10 100 1
01010
5 10 1 1
11111
5 1 10 1
11111
12 2 1 10
101110110101
2 100 1 10
00

3
52
5
10
16
22