Server Time:

User's AC Ratio in this contest

66.7% (10/15)

Submission's AC Ratio in this contest

34.5% (10/29)

Description

消消樂這種遊戲非常有名,主要的玩法,是一個長方形的畫面中,有許多不同顏色的石頭,點擊某一種顏色的石頭之後,與它相連的同顏色的石頭都會跟著消失,並獲得分數(消去的石頭愈多,得到的分數也愈多),而石頭會往下掉,將空白區域補起來。

我現在很想玩這個遊戲,但是這個遊戲對我來說太複雜了,於是我就自己改了一些遊戲規則。

新規則:

  • 遊戲畫面寬度為 $1$,高度為 $N$,如下圖
    (假設 $N = 4$,每個格子代表一個石頭)

  • 顏色只有黑色、白色兩種(黑色用 $B$ 表示,白色用 $W$ 表示)

  • 石頭落下的規則不變,但是消除後不會有新的石頭補上;
    也就是說有辦法把所有的石頭都消完

  • 消除方式:在一次操作中玩家可以自己決定要消除幾顆石頭(至少一顆),但是要消除的所有石頭必須相連且同色
    例如可以消除 BBBWWWWW 、 BBBWWWWW 的紅色部分,但是無法消除 BBBWWWWW 、 BBBWWWWW

    為了方便起見,上面的例子都將遊戲版面順時針旋轉 $90^\omicron$ 來表示

  • 計分方式:遊戲開始之前給定兩個參數 $a$ 和 $b$,每次操作消除 $x$ 個石頭可以獲得 $a \cdot x + b$ 分

  • 石頭消完後遊戲結束

雖然修改規則後,我玩得很開心,但是都沒辦法獲得高分,
請你寫一個程式,讓我知道可以得到的最高分數。

Input Format

第一行有一個整數 $T$,代表有幾筆測資(一筆測資代表一場遊戲);
接著每筆測資由兩行組成,第一行有三個整數 $N,a,b$,
第二行則是一個長度為 $N$ 的字串,代表遊戲的初始狀態,
字串中只有可能出現 BW

  • $1\leq T\leq 2000$
  • $1\leq N\leq 100$
  • $-100 \leq a, b \leq 100$

Output Format

每筆測資請輸出一個整數,代表該次遊戲能獲得的最高分數。

Sample Input 1

3
3 2 0
WWW
5 -2 5
BBWWB
6 1 -4
BWWBBB

Sample Output 1

6
15
-2

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~9 $0 \leq a, b \leq 100$ 30
2 0~29 無特別限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 65536 1 2
1 2000 65536 65536 1 2
2 2000 65536 65536 1 2
3 2000 65536 65536 1 2
4 2000 65536 65536 1 2
5 2000 65536 65536 1 2
6 2000 65536 65536 1 2
7 2000 65536 65536 1 2
8 2000 65536 65536 1 2
9 2000 65536 65536 1 2
10 2000 65536 65536 2
11 2000 65536 65536 2
12 2000 65536 65536 2
13 2000 65536 65536 2
14 2000 65536 65536 2
15 2000 65536 65536 2
16 2000 65536 65536 2
17 2000 65536 65536 2
18 2000 65536 65536 2
19 2000 65536 65536 2
20 2000 65536 65536 2
21 2000 65536 65536 2
22 2000 65536 65536 2
23 2000 65536 65536 2
24 2000 65536 65536 2
25 2000 65536 65536 2
26 2000 65536 65536 2
27 2000 65536 65536 2
28 2000 65536 65536 2
29 2000 65536 65536 2