← 返回题目列表

Codeforces · 1440/A

A. 购买字符串

中文机器翻译题面 查看原题

给定四个整数 $$$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$$$。

输出

对于每个测试用例,打印一个整数 - 购买该字符串所需的最小硬币数量。

示例

输入 #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

输出 #1

3
52
5
10
16
22

注意

在第一个测试用例中,您可以购买所有角色并支付 $$$3$$$ 硬币,因为 $$$0$$$ 和 $$$1$$$ 两个角色都花费 $$$1$$$ 硬币。

在第二个测试用例中,您可以首先将字符串的第$$$2$$$个和第$$$4$$$个符号从$$$1$$$更改为$$$0$$$,并为此支付$$$2$$$硬币。您的字符串将为 $$$00000$$$。之后,您可以购买该字符串并支付 $$$5 \cdot 10 = 50$$$ 硬币。支付的硬币总数为$$$2 + 50 = 52$$$。