달과 우산

Cody-Jamal은 이지러지는 달과 접힌 우산이 한 줄로 늘어선 벽화라는 최신 추상 미술 작품을 작업하고 있다. 안타깝게도 탐욕스러운 저작권 사냥꾼들은 이지러지는 달이 대문자 C처럼 보이고 접힌 우산이 J처럼 보인다고 주장하며, CJ와 JC에 대한 저작권을 보유하고 있다. 따라서 벽화에 CJ가 나타날 때마다 Cody-Jamal은 $\mathbf{X}$을 지불해야 하고, JC가 나타날 때마다 $\mathbf{Y}$을 지불해야 한다.

Cody-Jamal은 그들이 자신의 예술을 훼손하도록 내버려 둘 생각이 없으므로 이미 그린 것은 아무것도 바꾸지 않을 것이다. 하지만 아직 남아 있는 빈 공간을 전략적으로 채워 저작권 비용을 최소화할 수 있다고 판단했다.

예를 들어 CJ?CC?가 벽화의 현재 상태를 나타내며, C는 이지러지는 달을, J는 접힌 우산을, ?는 이지러지는 달이나 접힌 우산 중 하나를 아직 그려 넣어야 하는 공간을 나타낸다고 하자. 그는 벽화를 CJCCCC, CJCCCJ, CJJCCC, 또는 CJJCCJ로 완성할 수 있다. 첫 번째와 세 번째 선택지는 저작권료로 $\mathbf{X} + \mathbf{Y}$을 지불해야 하고, 두 번째와 네 번째 선택지는 $2 \cdot \mathbf{X} + \mathbf{Y}$을 지불해야 한다.

비용 $\mathbf{X}$와 $\mathbf{Y}$, 그리고 벽화의 현재 상태를 나타내는 문자열이 주어질 때, Cody-Jamal이 비용을 최소화하는 방식으로 벽화를 완성하면 저작권료로 얼마를 지불해야 하는가?

제한

시간 제한: 10초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $\mathbf{S}$의 각 문자는 C, J, ? 중 하나이다.

테스트 세트 1 (Visible Verdict)

$\mathbf{S}$의 길이는 $1 \le$ $\le 10$. $1 \le \mathbf{X} \le 100$. $1 \le \mathbf{Y} \le 100$.

테스트 세트 2 (Visible Verdict)

$\mathbf{S}$의 길이는 $1 \le$ $\le 1000$. $1 \le \mathbf{X} \le 100$. $1 \le \mathbf{Y} \le 100$.

추가 점수!

일부 저작권 보유자가 대가를 받는 대신 광고비를 Cody-Jamal에게 지불할 수도 있다면 어떻게 될까? Cody-Jamal이 돈을 받는 것은 음수 비용으로 나타낸다.

테스트 세트 3 (Hidden Verdict)

$\mathbf{S}$의 길이는 $1 \le$ $\le 1000$. $-100 \le \mathbf{X} \le 100$. $-100 \le \mathbf{Y} \le 100$.

입력의 첫째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 줄이 주어진다. 각 줄에는 두 비용과 벽화의 현재 상태를 각각 나타내는 두 정수 $\mathbf{X}$와 $\mathbf{Y}$, 그리고 문자열 $\mathbf{S}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$은 (1부터 시작하는) 테스트 케이스 번호이고, $y$은 완성된 벽화에 대해 Cody-Jamal이 저작권료로 지불해야 하는 최소 비용이다.

예제 케이스 #1은 문제 설명에서 다룬 예제이다. 최소 비용은 $\mathbf{X} + \mathbf{Y} = 2 + 3 = 5$이다.

예제 케이스 #2에서 Cody-Jamal은 이미 벽화를 완성했으므로 선택의 여지가 없다. 그의 벽화에는 CJ가 두 개, JC가 하나 있다.

예제 케이스 #3에서는 C와 J 중 어느 것으로 치환하든, 각각 둘째 문자와 셋째 문자 또는 첫째 문자와 둘째 문자에서 CJ가 하나 생긴다.

예제 케이스 #4에서 Cody-Jamal은 벽화를 모두 J로 채워 완성할 수 있다. 여기에는 CJ도 JC도 하나도 없으므로 저작권 비용이 발생하지 않는다.

추가 예제 - 테스트 세트 3

테스트 세트 3의 예제 케이스 #1에서 Cody-Jamal은 벽화를 JCJJCC 또는 JCJJJC로 완성하면 최적이다. 어느 쪽이든 그의 벽화에는 CJ가 하나, JC가 두 개 있다.