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 \le |s| \leq 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 \leq x, y \leq 10^6$).


-----Output-----

Output a single integer — the minimum number of angry comments.


-----Examples-----

Input
0?1
2 3
Output
4
Input
?????
13 37
Output
0
Input
?10?
239 7
Output
28
Input
01101001
5 7
Output
96


-----Note-----

In the first example one of the optimum ways to replace is 001. Then there will be $2$ subsequences 01 and $0$ subsequences 10. Total number of angry comments will be equal to $2 \cdot 2 + 0 \cdot 3 = 4$.

In the second example one of the optimum ways to replace is 11111. Then there will be $0$ subsequences 01 and $0$ subsequences 10. Total number of angry comments will be equal to $0 \cdot 13 + 0 \cdot 37 = 0$.

In the third example one of the optimum ways to replace is 1100. Then there will be $0$ subsequences 01 and $4$ subsequences 10. Total number of angry comments will be equal to $0 \cdot 239 + 4 \cdot 7 = 28$.

In the fourth example one of the optimum ways to replace is 01101001. Then there will be $8$ subsequences 01 and $8$ subsequences 10. Total number of angry comments will be equal to $8 \cdot 5 + 8 \cdot 7 = 96$.

Difficulty: HARD
Tags: String algorithms

Complete search

Implementation

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def solve(s, x, y):
	c0 = 0
	c1 = 0
	r = 0
	for i in s:
		if i == '0':
			c0 += 1
		else:
			r += c0 * x
			c1 += 1
	z0 = 0
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '0':
			z0 += 1
		else:
			r += z0 * y
	ans = r
	l0 = 0
	l1 = 0
	for i in s:
		if i == '?':
			r -= l0 * x + c0 * y
			c1 -= 1
			r += l1 * y + c1 * x
			l0 += 1
		elif i == '0':
			l0 += 1
			c0 -= 1
		else:
			l1 += 1
			c1 -= 1
		ans = min(ans, r)
	return ans
s = input().strip()
(x, y) = map(int, input().split())
if x <= y:
	print(solve(s, x, y))
else:
	s1 = s.replace('0', 'z')
	s1 = s1.replace('1', '0')
	s1 = s1.replace('z', '1')
	print(solve(s1, y, x))


s = list(input())
(y, k) = map(lambda x: int(x), input().split())

def Kurisu(v, y_01, x_10):
	c_x = [0] * len(v)
	(one, two) = (0, 0)
	q = 0
	for i in range(len(v)):
		i = len(v) - i - 1
		c_x[i] = [one, two]
		if v[i] == '1' or (y_01 <= x_10 and v[i] == '?'):
			one += 1
			q += c_x[i][1] * x_10
		else:
			two += 1
			q += c_x[i][0] * y_01
	qm = q
	(one, two) = (0, 0)
	for i in range(len(v)):
		if v[i] == '1':
			one += 1
		elif v[i] == '0':
			two += 1
		else:
			if y_01 > x_10:
				q -= one * x_10 + c_x[i][0] * y_01 - two * y_01 - c_x[i][1] * x_10
				one += 1
			else:
				q -= -+one * x_10 - c_x[i][0] * y_01 + two * y_01 + c_x[i][1] * x_10
				two += 1
			if qm > q:
				qm = q
	print(qm)
Kurisu(s, y, k)


s = input()
(x, y) = map(int, input().split())
if x > y:
	(x, y) = (y, x)
	s = s.replace('1', '#').replace('0', '1').replace('#', '0')
assert x <= y
z = y - x
s_if_all_ones = s.replace('?', '1')
ones_before = 0
zeros_before = 0
result = 0
for char in s_if_all_ones:
	if char == '0':
		result += ones_before * y
		zeros_before += 1
	else:
		assert char == '1'
		result += zeros_before * x
		ones_before += 1
best_result = result
zeros_n = zeros_before
ones_n = ones_before
zeros_before = 0
ones_before = 0
for char in s:
	if char == '0':
		zeros_before += 1
	elif char == '1':
		ones_before += 1
	else:
		assert char == '?'
		ones_n -= 1
		result += (ones_before - (zeros_n - zeros_before)) * z + (ones_n - zeros_n) * x
		if best_result > result:
			best_result = result
		zeros_n += 1
		zeros_before += 1
print(best_result)


def Kurisu_delta(v, y_01, x_10):
	c_x = [0] * len(v)
	one = 0
	two = 0
	q = 0
	for i in range(len(v)):
		i = len(v) - i - 1
		c_x[i] = [one, two]
		if v[i] == '1':
			one += 1
			q += c_x[i][1] * x_10
		elif v[i] == '0':
			two += 1
			q += c_x[i][0] * y_01
		elif y_01 <= x_10:
			one += 1
			q += c_x[i][1] * x_10
		else:
			two += 1
			q += c_x[i][0] * y_01
	one = 0
	two = 0
	d_one = 0
	d_two = 0
	qm = q
	for i in range(len(v)):
		if v[i] == '1':
			one += 1
		elif v[i] == '0':
			two += 1
		else:
			if qm > q:
				qm = q
			if y_01 > x_10:
				q -= (d_one + one) * x_10 + c_x[i][0] * y_01 - (d_two + two) * y_01 - c_x[i][1] * x_10
				one += 1
			else:
				q -= -(d_one + one) * x_10 - c_x[i][0] * y_01 + (d_two + two) * y_01 + c_x[i][1] * x_10
				two += 1
			if qm > q:
				qm = q
	print(qm)
s = list(input())
(y, k) = map(lambda x: int(x), input().split())
Kurisu_delta(s, y, k)