You've got a string $a_1, a_2, \dots, a_n$, consisting of zeros and ones.

Let's call a sequence of consecutive elements $a_i, a_{i + 1}, \ldots, a_j$ ($1\leq i\leq j\leq n$) a substring of string $a$. 

You can apply the following operations any number of times:  Choose some substring of string $a$ (for example, you can choose entire string) and reverse it, paying $x$ coins for it (for example, «0101101» $\to$ «0111001»);  Choose some substring of string $a$ (for example, you can choose entire string or just one symbol) and replace each symbol to the opposite one (zeros are replaced by ones, and ones — by zeros), paying $y$ coins for it (for example, «0101101» $\to$ «0110001»). 

You can apply these operations in any order. It is allowed to apply the operations multiple times to the same substring.

What is the minimum number of coins you need to spend to get a string consisting only of ones?


-----Input-----

The first line of input contains integers $n$, $x$ and $y$ ($1 \leq n \leq 300\,000, 0 \leq x, y \leq 10^9$) — length of the string, cost of the first operation (substring reverse) and cost of the second operation (inverting all elements of substring).

The second line contains the string $a$ of length $n$, consisting of zeros and ones.


-----Output-----

Print a single integer — the minimum total cost of operations you need to spend to get a string consisting only of ones. Print $0$, if you do not need to perform any operations.


-----Examples-----
Input
5 1 10
01000

Output
11

Input
5 10 1
01000

Output
2

Input
7 2 3
1111111

Output
0



-----Note-----

In the first sample, at first you need to reverse substring $[1 \dots 2]$, and then you need to invert substring $[2 \dots 5]$. 

Then the string was changed as follows:

«01000» $\to$ «10000» $\to$ «11111».

The total cost of operations is $1 + 10 = 11$.

In the second sample, at first you need to invert substring $[1 \dots 1]$, and then you need to invert substring $[3 \dots 5]$. 

Then the string was changed as follows:

«01000» $\to$ «11000» $\to$ «11111».

The overall cost is $1 + 1 = 2$.

In the third example, string already consists only of ones, so the answer is $0$.

Difficulty: competition

Starter code:

Solutions:
n, x, y = map(int, input().split())
a = input()
cnt = 0
prev = '1'
for ai in a:
  if prev == '1' and ai == '0': cnt += 1
  prev = ai
if cnt == 0:
  print(0)
else:
  print(min(x,y)*(cnt-1)+y)

n, x, y = map(int, input().split());
s = input()
ne = 0;
count = 0;
for i in range(1, n + 1):
    if (s[i - 1]  == '0'):
        count += 1;
    if (s[i - 1] == '1' or (s[i - 1] == '0' and i > 1 and s[i - 2] == '0')):
        p = ne;
    elif count == 1:
        ne += y;
        
    else:
        ne += min(x, y);
print(ne)

#
#           _____                    _____                    _____          
#          /\    \                  /\    \                  /\    \         
#         /::\____\                /::\    \                /::\____\        
#        /:::/    /               /::::\    \              /:::/    /        
#       /:::/    /               /::::::\    \            /:::/    /         
#      /:::/    /               /:::/\:::\    \          /:::/    /          
#     /:::/____/               /:::/__\:::\    \        /:::/____/           
#    /::::\    \               \:::\   \:::\    \      /::::\    \           
#   /::::::\    \   _____    ___\:::\   \:::\    \    /::::::\    \   _____  
#  /:::/\:::\    \ /\    \  /\   \:::\   \:::\    \  /:::/\:::\    \ /\    \ 
# /:::/  \:::\    /::\____\/::\   \:::\   \:::\____\/:::/  \:::\    /::\____\
# \::/    \:::\  /:::/    /\:::\   \:::\   \::/    /\::/    \:::\  /:::/    /
#  \/____/ \:::\/:::/    /  \:::\   \:::\   \/____/  \/____/ \:::\/:::/    / 
#           \::::::/    /    \:::\   \:::\    \               \::::::/    /  
#            \::::/    /      \:::\   \:::\____\               \::::/    /   
#            /:::/    /        \:::\  /:::/    /               /:::/    /    
#           /:::/    /          \:::\/:::/    /               /:::/    /     
#          /:::/    /            \::::::/    /               /:::/    /      
#         /:::/    /              \::::/    /               /:::/    /       
#         \::/    /                \::/    /                \::/    /        
#          \/____/                  \/____/                  \/____/         
#
n, x, y = list(map(int, input().split()))
s = input()
cnt, tmp = 0, 0
for i in s:
    if i == '1':
        if tmp:
            cnt += 1
        tmp = 0
    else:
        tmp += 1
if tmp:
    cnt += 1
if cnt > 0:
    print(min(x, y)*(cnt-1)+y)
else:
    print(0)


n,x,y=map(int,input().split())
a=input()+"1"
cnt=a.count("01")
if cnt==0:
    print(0)
else:
    print((cnt-1)*min(x,y)+y)

n, x, y = map(int, input().split())
s = input()
cnt, tmp = 0, 0
for i in s:
    if i == '1':
        if tmp:
            cnt += 1
        tmp = 0
    else:
        tmp += 1
if tmp:
    cnt += 1
if cnt > 0:
    print(min(x, y)*(cnt-1)+y)
else:
    print(0)

n, x, y = list(map(int, input().split()))
p = len(input().replace('1', ' ').split())
print([0, (p - 1) * min(x, y) + y][p > 0])


n, a, b = map(int, input().split())
s = input()
k = sum(map(lambda x,y: x=='1' and y=='0', s, s[1:]))
k += s[0] == '0'
print (b+min(a,b)*(k-1) if k else 0)

n, x, y = map(int, input().split())
a = input()
if '0' not in a:
    print(0)
else:
    number_of_zero_groups = 0
    curr = a[0]
    if curr == '0':
        number_of_zero_groups += 1
    for e in a[1:]:
        if e == '0' and curr == '1':
            number_of_zero_groups += 1
        curr = e
    print((number_of_zero_groups-1) * min(x, y) + y)

def __starting_point():
    n,a,y=input().strip().split(' ')
    n,a,y=[int(n),int(a),int(y)]
    bin_str=str(input())
    p=0
    flag=0
    for x in range(0,len(bin_str)):
        if bin_str[x]=='0':
            flag=1
        elif bin_str[x]=='1' and flag==1:
            flag=0
            p+=1
    if flag==1 and bin_str[x-1]:
        p+=1
    #print(p)#***
    if p==0:
        print('0')
    else:
        ans=((p-1)*min(a,y))+y
        print(ans)
__starting_point()

n, x, y = list(map(int, input().split()))
a = '1' + input()
m = sum(1 for i in range(1, n+1) if a[i-1] == '1' and a[i] == '0')
ans = min( (x*i + y*(m-i) for i in range(m) ), default = 0)
print(ans)

from functools import cmp_to_key

s=input()
s=s.split(" ")
n=int(s[0])
x=int(s[1])
y=int(s[2])
s=input()
s=list(s)
s.append('2')
p=0
for i in range(1,len(s)):
    if s[i]!='0' and s[i-1]=='0':
        p+=1
if p==0:
    print(0)
else:
    print((p-1)*min(x,y)+y)



import re
cost=0
inp=input().split(' ')
string=input()
count0 = re.findall('0+', string)
if count0 and int(inp[1]) < int(inp[2]):
    cost += (len(count0)-1)*int(inp[1])+int(inp[2])
else:
    cost += len(count0)*int(inp[2])
print(cost)


def main():
    n, x, y = list(map(int, input().split()))
    s, zo, a = input(), [0, 0], ' '
    for b in s:
        if a != b:
            zo[b == '1'] += 1
            a = b
    z, o = zo
    if s[0] == '1':
        o -= 1
    if s[-1] == '1':
        o -= 1
    if o < 0:
        o = 0
    print(min(z * y, o * x + y))


def __starting_point():
    main()

__starting_point()


def count_components(line):
  in_zero_component = False
  num_components = 0
  for c in line:
    if c == '0':
      if not in_zero_component:
        num_components += 1
      in_zero_component = True
    else:
      in_zero_component = False
  return num_components

_, reverse_cost, invert_cost = [int(x) for x in input().split()]
line = input()
num_components = count_components(line)

cost = (num_components - 1) * min(reverse_cost, invert_cost) + invert_cost if num_components > 0 else 0
print(cost)


n, x, y = list(map(int,input().strip().split(' ')))
s = input()
groups = 0
if s[0] == '0':
    groups += 1
for b in range(1,n):
    if s[b] == '0' and s[b-1] == '1':
        groups += 1
if groups == 0:
    print(0)
else:
    print((groups - 1) * min(x,y) + y)

n, x, y = map(int, input("").split(" "))
texte = input("").split("1")
espace = texte.count('')
print(max(0, min((len(texte)-espace-1)*x+y, (len(texte)-espace)*y)))

a=input().split()
n=int(a[0])
x=int(a[1])
y=int(a[2])
a=input()
groups = 0
add=True
for i in range(n):
    if add==True and a[i]=='0':
        groups+=1
        add=False
    if a[i]=='1':
        add=True
tot1 = groups*y
tot2 = (groups-1)*x+y
if abs(tot1)>abs(tot2):
    print(tot2)
else:
    print(tot1)


n, x, y = list(map(int, input().split()))
s = input().replace('1', ' ')
z = len(s.split())
print(z and (z - 1) * min(x, y) + y)




# Made By Mostafa_Khaled


# 00101101001
n, x, y = list(map(int, input().split()))
line = input()
temp = line.split('1')
cnt = 0
#print(temp)
for i in temp:
    if len(i) > 0:
        cnt += 1
print(min(y*cnt, abs(y+x*(cnt-1))))


n, x, y = [int(x) for x in input().split()]
l = list(input())
l = ['1'] + l + ['1']
num = 0
for i in range(len(l) - 1):
    if l[i] == '1' and l[i + 1] == '0':
        num += 1
l = l[1:-1]
num1 = num * y
num2 = max(0, num * x - x + y)
print(min(num1, num2))


n,x,y =map(int,input().split())

ss = input().strip()

L = len(ss)

i = 0
last = -1
cnt = 0
while i<L :
    if ss[i] == '1' :
        if last == 0 : cnt += 1
        last = 1
    else :
        last = 0
    i += 1

if ss[L-1] == '0' : cnt += 1    

ans = 0

if x<y : ans = ( cnt - 1 ) * x + y
else : ans = cnt * y

if cnt == 0 : ans = 0

print(int(ans))

n,x,y =map(int,input().split())
ss = input().strip()
L = len(ss)
i = 0
last = -1
cnt = 0
while i<L :
    if ss[i] == '1' :
        if last == 0 : cnt += 1
        last = 1
    else :
        last = 0
    i += 1

if ss[L-1] == '0' : cnt += 1    

ans = 0

if x<y : ans = ( cnt - 1 ) * x + y
else : ans = cnt * y

if cnt == 0 : ans = 0

print(int(ans))