Currently, XXOC's rap is a string consisting of zeroes, ones, and question marks. Unfortunately, haters gonna hate. They will write x angry comments for every occurrence of subsequence 01 and y angry comments for every occurrence of subsequence 10. You should replace all the question marks with 0 or 1 in such a way that the number of angry comments would be as small as possible. String b is a subsequence of string a, if it can be obtained by removing some characters from a. Two occurrences of a subsequence are considered distinct if sets of positions of remaining characters are distinct. Input The first line contains string s— XXOC's rap (1≤|s|≤10 5). The second line contains two integers x and y— the number of angry comments XXOC will recieve for every occurrence of 01 and 10 accordingly (0≤x,y≤10 6). Output Output a single integer— the minimum number of angry comments. Examples Input Copy 0?1 2 3 Output Copy 4 Input Copy ????? 13 37 Output Copy 0 Input Copy ?10?