CF1550B Maximum Cost Deletion（分段比较）

You are given a string ss 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 ll, you get a⋅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.

Input

The first line contains a single integer tt (1≤t≤2000 ) — the number of testcases.

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

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

Output

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

Example

Input

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

Output

1. 6
2. 15
3. -2

大意

有一个01字符串，每次可以删去一段连续的0或1，删除一段长为  l 的字符串可得到 a∗l+b 分，求最大分数。

由于字符串最后必须变为空串，显然  a∗l 合并同类项后为  a∗n 故只需让 b  最大化即可。

由于  +b 的次数与删除次数有关所以分类讨论

• 当  b≥0 时，取的越多越好，操作 n 次
• 当  b<0 时，取得越少越好，可以证明，先全部删去连续区间数量较少的，再一下把另一个全删了，操作次数最少

举个例子 10011001

最优解： 10011001⇒1111⇒ 空串

错解    ：10011001⇒111001⇒001⇒1⇒ 空串

可见每个0串还是得单独删去，而1串删除的操作分为两步，故不如最优解。

具体实现看代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
      int c0=0,c1=0,ans=0; //chush
    int n,a,b;
    string s;
    cin>>n>>a>>b;
    cin>>s;
    if(b<0)
    {
      for(int i=0;i<n;i++)
      if(s[i]=='0')
      {
        int p=i;
        while(s[p]=='0')
        p++;
        i=p-1;
        c0++;
      }
     for(int i=0;i<n;i++)
      if(s[i]=='1')
      {
        int p=i;
        while(s[p]=='1')
        p++;
        i=p-1;
        c1++;
      }           
    ans=a*n+min(c1,c0)*b+b;
    }
    else
    ans=b*n+a*n;  
    cout<<ans<<endl;  
   } 
 }