1198: 神奇的字符串

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：24 Solved：2

Description

kunkun有一个神奇字符串，该字符串只由数字0和数字1组成。他想将这个字符串删除。他可以任意进行以下三种操作，每种操作的次数不限：
1）选择字符串中的一个0和一个1，将他们删除，代价为a；
2）选择字符串中两个位置不同的0或者两个位置不同的1，将他们删除，代价为b；
3）将字符串中的一个0变成1或将字符串中的一个1变成0，代价为c。
聪明的你能不能帮帮kunkun，求出将这条神奇字符串删除成空字符串的最小代价为多少？

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

第一行包括一个仅由数字0和数字1构成的字符串s，s的长度不超过50000,保证s的长度为偶数
第二行包括三个整数a、b、c，分别代表上述三种操作的代价。保证1≤a,b,c≤10000

Output

输出包括一个整数，表示删除该字符串的最小代价

Sample Input Copy 

0110011001
3 4 5

Sample Output Copy 

15

HINT

消除一个0和一个1有以下两种方案：

①直接消除花费a

②先花费c进行转换，再花费b消除

需要考虑b+c<a的情况

同理，消除两个0,或者两个1页需要考虑c+a<b的情况

Source/Category