Cho xâu \(S\) độ dài \(N\) chỉ chứa các ký tự latin in thường. Ta ký hiệu \(S_i\) \((1\le i\le N)\) là ký tự thứ \(i\) từ trái sang của xâu \(S\).
Bạn được phép thực hiện hai phép biến đổi sau lên \(S\) với một số lượng lần tùy ý:
- Bỏ ra \(A\) đồng để đưa ký tự đầu tiên bên trái của \(S\) sang tận cùng bên phải. Nói cách khác, sau khi áp dụng phép biến đổi này thì xâu \(\overline{S_1S_2S_3...S_N}\) sẽ trở thành \(\overline{S_2S_3...S_NS_1}\).
- Bỏ ra \(B\) đồng để gán \(S_i\) \((1\le i\le N)\) thành một ký tự latin in thường bất kỳ.
Cho biết các giá trị \(N\), \(A\), \(B\) và xâu \(S\) ở trạng thái ban đầu, hãy tìm cách biến đổi với chi phí thấp nhất để biến \(S\) trở thành một xâu đối xứng.
Ghi chú: Một xâu ký tự \(T\) được xem là xâu đối xứng nếu ta đọc nó từ trái qua phải cũng y hệt như đọc từ phải qua trái. Nói cách khác, nếu xâu \(T=\overline{T_1T_2...T_L}\) có \(T_1=T_L\), \(T_2=T_{L-1}\), \(T_3=T_{L-2}\),... thì nó là một xâu đối xứng.
Input
- Dòng đầu chứa ba số nguyên dương \(N\), \(A\), \(B\) \(\left(1\le N\le 5000, 1\le A,B\le 10^9\right)\).
- Dòng tiếp theo chứa xâu \(S\) độ dài \(N\) chỉ gồm các chữ cái latin in thường.
Output
- In ra chi phí nhỏ nhất để biến đổi \(S\) thành một xâu đối xứng.
Ví dụ
Sample input 01
5 1 2
aatvb
Sample output 01
3
Giải thích
Cách biến đổi tối ưu nhất sẽ tốn \(3\) đồng:
- Đầu tiên, bỏ ra \(2\) đồng để gán \(S_5=\)
t
. Sau đó, \(S=\)aatvt
. - Tiếp theo, bỏ ra \(1\) đồng để dịch chuyển \(S_1\) về cuối sau. Sau đó, \(S=\)
atvta
là một xâu đối xứng.