给定一个字符串 $$$s$$$,长度为 $$$n$$$,仅包含字符 0 和 1。
执行以下操作,直到字符串变空:选择一些连续的相同字符的子字符串,将其从字符串中删除,然后以相同的顺序将剩余的两个部分粘合在一起(其中任何一个都可以为空)。例如,如果从字符串 111110 中删除子字符串 111,您将得到字符串 110。当您删除长度为 $$$l$$$ 的子字符串时,您将获得 $$$a \cdot l + b$$$ 点。
如果您必须将给定的字符串留空,您的任务是计算您总共可以获得的最大分数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2000$$$) — 测试用例的数量。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \le n \le 100; -100 \le a, b \le 100$$$) — 字符串 $$$s$$$ 以及参数 $$$a$$$ 和 $$$b$$$ 的长度。
第二行包含字符串$$$s$$$。字符串 $$$s$$$ 仅包含字符 0 和 1。
输出
对于每个测试用例,打印一个整数 - 您可以获得的最大分数。
示例
输入 #1
3 3 2 0 000 5 -2 5 11001 6 1 -4 100111
输出 #1
6 15 -2
注意
在第一个例子中,删除整个字符串就足够了,然后我们将得到 $$$2 \cdot 3 + 0 = 6$$$ 点。
在第二个例子中,如果我们逐个删除字符,那么对于每个删除的字符,我们将获得 $$$(-2) \cdot 1 + 5 = 3$$$ 点,i。 e.总共 $$$15$$$ 积分。
在第三个例子中,我们可以从字符串 100111 中删除子字符串 00,我们得到 $$$1 \cdot 2 + (-4) = -2$$$ 点,字符串将等于 1111,将其完全删除我们得到 $$$1 \cdot 4 + (-4) = 0$$$ 点。总共,我们通过 $$$2$$$ 操作获得了 $$$-2$$$ 积分。