题目描述

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

执行以下操作直到字符串为空：选择某个连续的相同字符的子串，将其从字符串中删除，剩余两部分按原顺序合并（其中任何部分都可以为空）。

例如：如果从字符串 \(111110\) 中删除子串 \(111\)，则将获得字符串 \(110\)。

删除长度为 \(l\) 的子串，将获得奖励 \(a×l+b\)。

按上述操作直到字符串为空，你能获得总奖励的最大值是多少？

格式

输入格式

第一行一个正整数 \(t（1≤t≤2000）\)，表示测试组数；

每组数据输入两行，第一行三个整数 \(n,a,b（1≤n≤1000；-100≤a,b≤100）\)，如题意；

第二行输入一个长度为 \(n\) 的字符串 \(s\)，\(s\) 由 \(0\) 和 \(1\) 组成。

输出格式

对于每个测试组输出一行一个整数，表示总奖励的最大值。

样例1

样例输入1

3
3 2 0
000
5 -2 5
11001
6 1 -4
100111

样例输出1

6
15
-2

样例解释

第一组数据：一步将 \(000\) 删除，贡献 \(2×3+0=6\)

第二组数据：一个一个删除字符，贡献 \(5×(-2×1+5)=15\)

第三组数据：先删除 \(00\)，再删除 \(1111\)，贡献 \((1×2-4)+(1×4-4)=-2\)

限制

时间：\(1s\) 空间：\(256M\)

对于 \(20\%\) 的数据：\(1≤t≤2000；1≤n≤100\)；输入串全 \(0\)，或全 \(1\)。

对于 \(50\%\) 的数据：\(1≤t≤2000；1≤n≤100\)；

对于 \(100\%\) 的数据：\(1≤t≤2000；1≤n≤1000\)；

来源

地址：\(zloj,J2021\)域
作者：\(jialiang2509\)