You are given a string S  of numbers. Dr. Dragoon has eaten up some numbers of the string. You decide to fix the string by putting the numbers 0 and 1 in the empty spaces. 
The base cost for putting the ‘0’  is x  and putting ‘1’  is y . The cost of putting a number is the base cost multiplied by the number of times you use the letter till  that position (including   the position ).  The local mayor is happy with your work and commissions you for every number you put. 

More specifically ,  if you put , say 0  in 5th position, the mayor will count the number of occurrences of 0  till 5th   position and pay you the same amount. You wonder what the minimum cost for fixing the string is. Note  – The answer can also be negative, they denote that you got an overall profit.

Input Format: 

The input consists of 2 lines. First-line consists of the string of numbers S. ‘?’  denotes an empty position. 

The second line consists of 2 integers x,y, the base cost of 0 and 1. 

Output Format:  

Output 1 integer, the minimum cost of fixing the string.

Constraints :  

1<=|S|<=100

1<=x,y<=100 

Sample Input:  

501?1?

6 5

Sample Output:  

6

Sample Input:  

1001?11?

5  23

Sample Output:  

8

Explanation  :  

Fill 0 in the first place, the net cost will be 6-2=4. In the second place fill, 1 the net cost will be 5-3=2 Hence total cost is 4+2=6. 

In second test case we will fill both spaces with zero , filling first zero costs  1*5-3=2 and filling the other zero costs  2*5  - 4 =6  , so total being 8.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def ans(n, a, b):
	if n == act:
		return 0
	if dp[n][a][b] != -1:
		return dp[n][a][b]
	if l[n] == '0':
		dp[n][a][b]
		return ans(n + 1, a + 1, b)
	elif l[n] == '1':
		dp[n][a][b] = ans(n + 1, a, b + 1)
		return ans(n + 1, a, b + 1)
	elif l[n] == '?':
		dp[n][a][b] = min((a - l1[n] + 1) * x - (a + 1) + ans(n + 1, a + 1, b), (b - l2[n] + 1) * y - (b + 1) + ans(n + 1, a, b + 1))
		return min((a - l1[n] + 1) * x - (a + 1) + ans(n + 1, a + 1, b), (b - l2[n] + 1) * y - (b + 1) + ans(n + 1, a, b + 1))
	else:
		dp[n][a][b] = ans(n + 1, a, b)
		return ans(n + 1, a, b)
l = str(input())
(x, y) = map(int, input().split())
dp = [[[-1 for i in range(101)] for j in range(101)] for k in range(101)]
l1 = []
l2 = []
c = 0
k = 0
for i in l:
	if i == '1':
		c += 1
	if i == '0':
		k += 1
	l1.append(k)
	l2.append(c)
act = len(l)
dd = ans(0, 0, 0)
print(dd)