Mô tả và yêu cầu

ABGAME3

Trò chơi ABGAME3 là một trò chơi trên một xâu ký chỉ gồm các các ký tự A, B, #. Người chơi
có thể thay đổi trạng thái xâu bằng việc thực hiện dãy các bước biến đổi, mỗi bước biến đổi như
sau:

 Chọn một vị trí là ký tự A hoặc B rồi loại bỏ, sau khi loại bỏ ký tự ở vị trí này thay bằng
ký tự # và các ký tự nằm ở vị trí kề với vị trí này sẽ bị biến đổi, cụ thể nếu là ký tự A sẽ bị
biến đổi thành ký tự B, nếu là ký tự B sẽ bị biến đổi thành ký tự A.
 Chi phí của bước biến đổi này là tổng các chi phí: nếu kề với một ký tự A mất x, nếu kề
với ký tự B mất y, nếu kề với ký tự # mất z.

Nhiệm vụ của người chơi là từ một trạng thái ban đầu tìm cách thực hiện dãy các bước biến đổi để
nhận được trạng thái xâu chỉ gồm các ký tự # với chi phí nhỏ nhất.

Yêu cầu: Cho biết trạng thái ban đầu, hãy tìm cách biến đổi thỏa mãn.

Dữ liệu vào

 Dòng đầu chứa 3 số nguyên không âm x, y, z (x, y, z ≤ 106).

 Dòng thứ hai chứa một xâu chỉ gồm các ký tự A, B hoặc #.

Dữ liệu ra

 Gồm một dòng ghi chi phí nhỏ nhất.

ABGAME3.INP ABGAME3.OUT
10 1 1 4
BAB

Subtask 1: Giả thiết là n ≤ 10.
Subtask 2: Giả thiết là n ≤ 15.
Subtask 3: Giả thiết là n ≤ 100.