CF1550B.Maximum Cost Deletion

You are given a string $s$ of length $n$ consisting only of the characters 0 and 1.

You perform the following operation until the string becomes empty: choose some consecutive substring of equal characters, erase it from the string and glue the remaining two parts together (any of them can be empty) in the same order. For example, if you erase the substring 111 from the string 111110, you will get the string 110. When you delete a substring of length $l$, you get $a \cdot l + b$ points.

Your task is to calculate the maximum number of points that you can score in total, if you have to make the given string empty.

给你一个长度为 $n$ 的字符串 $s$，该字符串仅由字符 0 和 1 组成。

你将执行以下操作，直到字符串变为空：选择一段由相同字符组成的连续子串，将其从字符串中删除，并将剩余的左右两部分（其中任一部分可以为空）按原顺序拼接起来。例如，若从字符串 111110 中删除子串 111，则得到字符串 110。当你删除长度为 $l$ 的子串时，你将获得 $a \cdot l + b$ 分。

你的任务是：在必须将给定字符串清空的前提下，计算所能获得的总分的最大值。

The first line contains a single integer $t$ ($1 \le t \le 2000$) — the number of testcases.

The first line of each testcase contains three integers $n$, $a$ and $b$ ($1 \le n \le 100; -100 \le a, b \le 100$) — the length of the string $s$ and the parameters $a$ and $b$.

The second line contains the string $s$. The string $s$ consists only of the characters 0 and 1.

第一行包含一个整数 $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 组成。

For each testcase, print a single integer — the maximum number of points that you can score.

对于每个测试用例，输出一个整数——你能获得的最高分数。

In the first example, it is enough to delete the entire string, then we will get $2 \cdot 3 + 0 = 6$ points.

In the second example, if we delete characters one by one, then for each deleted character we will get $(-2) \cdot 1 + 5 = 3$ points, i. e. $15$ points in total.

In the third example, we can delete the substring 00 from the string 100111, we get $1 \cdot 2 + (-4) = -2$ points, and the string will be equal to 1111, removing it entirely we get $1 \cdot 4 + (-4) = 0$ points. In total, we got $-2$ points for $2$ operations.

在第一个例子中，只需删除整个字符串，即可获得 $2 \cdot 3 + 0 = 6$ 分。

在第二个例子中，若逐个删除字符，则每删除一个字符可获得 $(-2) \cdot 1 + 5 = 3$ 分，即总共获得 $15$ 分。

在第三个例子中，我们可以从字符串 100111 中删除子串 00，获得 $1 \cdot 2 + (-4) = -2$ 分，剩余字符串变为 1111；再将该字符串全部删除，可获得 $1 \cdot 4 + (-4) = 0$ 分。总计进行了 $2$ 次操作，共获得 $-2$ 分。