There are $n$ consecutive seat places in a railway carriage. Each place is either empty or occupied by a passenger.

The university team for the Olympiad consists of $a$ student-programmers and $b$ student-athletes. Determine the largest number of students from all $a+b$ students, which you can put in the railway carriage so that:  no student-programmer is sitting next to the student-programmer;  and no student-athlete is sitting next to the student-athlete. 

In the other words, there should not be two consecutive (adjacent) places where two student-athletes or two student-programmers are sitting.

Consider that initially occupied seat places are occupied by jury members (who obviously are not students at all).


-----Input-----

The first line contain three integers $n$, $a$ and $b$ ($1 \le n \le 2\cdot10^{5}$, $0 \le a, b \le 2\cdot10^{5}$, $a + b > 0$) — total number of seat places in the railway carriage, the number of student-programmers and the number of student-athletes.

The second line contains a string with length $n$, consisting of characters "." and "*". The dot means that the corresponding place is empty. The asterisk means that the corresponding place is occupied by the jury member.


-----Output-----

Print the largest number of students, which you can put in the railway carriage so that no student-programmer is sitting next to a student-programmer and no student-athlete is sitting next to a student-athlete.


-----Examples-----
Input
5 1 1
*...*

Output
2

Input
6 2 3
*...*.

Output
4

Input
11 3 10
.*....**.*.

Output
7

Input
3 2 3
***

Output
0



-----Note-----

In the first example you can put all student, for example, in the following way: *.AB*

In the second example you can put four students, for example, in the following way: *BAB*B

In the third example you can put seven students, for example, in the following way: B*ABAB**A*B

The letter A means a student-programmer, and the letter B — student-athlete.

Difficulty: interview

Starter code:

Solutions:
n, a, b = list(map(int, input().split()))
s = input()
s += '*'
n += 1
m = []
i = 0
i1 = -1
while i < len(s):
    if s[i] == '*':
        if i - i1 > 1:
            m.append(i - i1 - 1)
        i1 = i
    i += 1
sm = a + b
for c in m:
    if c % 2 == 0:
        a = max(0, a - c // 2)
        b = max(0, b - c // 2)
    else:
        if a > b:
            a = max(0, a - (c + 1) // 2)
            b = max(0, b - c // 2)
        else:
            b = max(0, b - (c + 1) // 2)
            a = max(0, a - c // 2)
print(sm - a - b)


def inpmap():
    return list(map(int, input().split()))
n, a, b = inpmap()
arr = list(input())
s = 0 if a > b else 1
ix = [a, b]
res = 0
for i in range(n):
    if arr[i] == '.':
        if ix[s] > 0:
            ix[s] -= 1
            res += 1
        s = 1 - s
    else:
        s = 0 if ix[0] > ix[1] else 1
print(res)


def main():
    n, a, b = list(map(int, input().split()))
    t = a + b
    s = input()
    last = -1
    for c in s:
        if c == '.':
            if last == -1:
                if a >= b and a > 0:
                    last = 0
                    a -= 1
                elif b >= a and b > 0:
                    last = 1
                    b -= 1
            elif last == 0 and b > 0:
                last = 1
                b -= 1
            elif last == 1 and a > 0:
                last = 0
                a -= 1
            else:
                last = -1
        else:
            last = -1

    print(t - a - b)

main()


import atexit
import io
import sys
import math

# Buffering IO
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
    

def main():
    n, a, b = [int(x) for x in input().split()]
    s = input()
    
    if a<b:
        a,b = b,a
    cc = 0
    tt = 0
    for c in s:
        if c == '.':
            cc+=1
        else:
            aa = math.ceil(cc/2)
            bb = math.floor(cc/2)
            tt += min (aa, a) + min(bb,b)
            a = max(a-aa, 0)
            b = max(b-bb, 0)
            if a<b:
                a,b = b,a
            cc = 0
    aa = math.ceil(cc/2)
    bb = math.floor(cc/2)
    tt += min (aa, a) + min(bb,b)
    a = max(a-aa, 0)
    b = max(b-bb, 0)
    
    print(tt)

    
def __starting_point():
    main()

__starting_point()

n, a, b = map(int, input().split())
total = a + b
s = input()
prev_took = 'none'
for i in range(n):
  if a == 0 and b == 0:
    break
  if s[i] == '.' and prev_took == 'none':
    if a > b:
      a -= 1
      prev_took = 'a'
    else:
      b -= 1
      prev_took = 'b'
  elif s[i] == '.' and prev_took == 'a':
    if b > 0:
      b -= 1
      prev_took = 'b'
    else:
      prev_took = 'none'
  elif s[i] == '.' and prev_took == 'b':
    if a > 0:
      a -= 1
      prev_took = 'a'
    else:
      prev_took = 'none'
  elif s[i] == '*':
    prev_took = 'none'
print(total - a - b)

n, p, s = map(int, input().split())
q = input()
a = []
x = 0
for i in q:
    if (i == '*' and x):
        a.append(x)
        x = 0
    elif i == '.':
        x += 1
if (x):
    a.append(x)

ans = 0
lena = len(a)
for i in range(lena):
    if (p > s):
        ans += min(a[i] // 2 + a[i] % 2, p)
        p -= min(a[i] // 2 + a[i] % 2, p)
        ans += min(a[i] // 2, s)
        s -= min(a[i] // 2, s)
    else:
        ans += min(a[i] // 2 + a[i] % 2, s)
        s -= min(a[i] // 2 + a[i] % 2, s)
        ans += min(a[i] // 2, p)
        p -= min(a[i] // 2, p)        
print(ans)

n, a, b = [int(x) for x in input().split()]

a, b = sorted([a, b])
total = a + b

from itertools import groupby
s = input().strip()

for val, g in groupby(s):
    if val == '*': continue
    length = len(list(g))
    b -= (length + 1) // 2
    a -= length // 2
    if a > b:
        a, b = b, a

a = max(a, 0)
b = max(b, 0)

print(total - a - b)


N, A, B = map(int, input().split())
S = list(input())

cnt = 0
if S[0] == ".":
    if A > B and A > 0:
        S[0] = "A"
        A -= 1
        cnt += 1
    elif B > 0:
        S[0] = "B"
        B -= 1
        cnt += 1

for i in range(1, len(S)):
    if S[i] == ".":
        if S[i-1] == "*" or S[i-1] == ".":
            if A > B:
                S[i] = "A"
                A -= 1
                cnt += 1
            elif B > 0:
                S[i] = "B"
                B -= 1
                cnt += 1
        elif S[i-1] == "A":
            if B > 0:
                S[i] = "B"
                B -= 1
                cnt += 1
        else:
            if A > 0:
                S[i] = "A"
                A -= 1
                cnt += 1

print(cnt)

from math import ceil
from math import floor

while True:

    inp = input().split()

    n = int(inp[0])
    a = int(inp[1])
    b = int(inp[2])

    components = input().split('*')

    max_students = 0

    for c in components:

        max_a_b = min( len(c)//2 + len(c)%2, max(a, b) )

        min_a_b = min( len(c)//2, min(a, b) )

        max_students += max_a_b + min_a_b

        if a>=b:

            a -= max_a_b
            b -= min_a_b

        else:

            a -= min_a_b
            b -= max_a_b

    print(max_students)

    break


(n, a, b) = list(map(int, input().split()))

lst = list(input())

k = 0
array = []
for x in range(n):
    if lst[x] == '*':
        array.append(k)
        k = 0
    else:
        k += 1

if lst[0] == '*':
    array = array[1:]
if lst[-1] != '*':
    array.append(k)

s = a + b
for x in array:
    if max(a, b) == a:
        p = (x + 1) // 2
        a = max(a - p, 0)
        b = max(b - (x - p), 0)
    else:
        p = (x + 1) // 2
        b = max(b - p, 0)
        a = max(a - (x - p), 0)

print(s - (a + b))


n, a, b = map(int, input().split())
s = input()

last = ''
total = 0

for c in s:
    if c == '.':
        if not last in ['a', 'b']:
            if a >= b and a > 0:
                last = 'a'
                total += 1
                a -= 1
            elif b >= a and b > 0:
                last = 'b'
                total += 1
                b -= 1
            else:
                last = c
        elif last == 'a':
            if b > 0:
                last = 'b'
                total += 1
                b -= 1
            else:
                last = '.'
        else:
            if a > 0:
                last = 'a'
                total += 1
                a -= 1
            else:
                last = '.'
    else:
        last = c

print(total)

def read_data():
    n, k, l = map(int, list(input().strip().split()))
    a = list(input().strip())
    return n, k, l, a

def solve(k,l):
    tot = 0
    last = "*"
    for ch in a:
        if k == 0 and l == 0:
            return tot
        if ch == ".":
            if last == "k":
                if l>0:
                    l -= 1
                    tot += 1
                    last = "l"
                else:
                    last = "*"
            elif last == "l":
                if k>0:
                    k -= 1
                    tot += 1
                    last = "k"
                else:
                    last = "*"
            elif last == "*":
                if k>l:
                    k -= 1
                    last = "k"
                else:
                    l -= 1
                    last = "l"
                tot += 1
        else:
            last = "*"
    return tot

n, k, l, a = read_data()
print(solve(k,l))

n,a,b=list(map(int,input().split()))
s=input()
ans=0

A,B=a,b
cnt=0
for i in s:
    if(i=='*'):
        if(cnt%2):
            if(a>b):
                a-=cnt//2+1
                b-=cnt//2
            else:
                a-=cnt//2
                b-=cnt//2+1             
        else:
            a-=cnt//2
            b-=cnt//2
        cnt=0
    else:
        cnt+=1
if(cnt%2):
    if(a>b):
        a-=cnt//2+1
        b-=cnt//2
    else:
        a-=cnt//2
        b-=cnt//2+1             
else:
    a-=cnt//2
    b-=cnt//2
cnt=0

#print(a,b)
if(a<=0):
    if(b<=0):
        print(A+B)
    else:
        print(A+B-b)
else:
    if(b<=0):
        print(A-a+B)
    else:
        print(A-a+B-b)



n, a, b = list(map(int, input().split()))
s = input()
just_placed = None
ans = 0

##def place(x):
##    assert(x in 'ab')
##    nonlocal a, b, just_placed, ans
##    if x == 'a':
##        if a > 0:
##            a-=1
##            ans+=1
##            just_placed=a
##        else:
##            just_placed=None
##    elif x == 'b':
        

for i in s:
    more_a = (a > b) #When a moon hits your eye like a big pizza pie, that's...
    if i == '.':
        if just_placed == 'a':
            if b > 0:
                b-=1
                ans+=1
                just_placed = 'b'
            else:
                just_placed = None
        elif just_placed == 'b':
            if a > 0:
                a-=1
                ans+=1
                just_placed = 'a'
            else:
                just_placed=None
        else:
            if more_a:
                a-=1
                ans+=1
                just_placed='a'
            else:
                if b>0:
                    b-=1
                    ans+=1
                    just_placed='b'
                else:
                    just_placed = None
                
    else:
        just_placed = None
print(ans)


import re
R = lambda: list(map(int, input().split()))

n, a, b = R()
s = input()

s0 = a + b
for t in re.findall(r'\.+', s):
    t = len(t)
    if t % 2:
        if a > b: a -= 1
        else: b -= 1
        t -= 1
    a -= t/2
    b -= t/2

print(int(s0 - max(0,a) - max(0,b)))


n,s1,s2 = (list(map(int,input().split())))
a = input()
p = 0
f = 0
for i in range(n):
    if a[i] == '*':
        f = 0
        continue
    if s1 == 0 and f == 2:
        f = 0
        continue
    if s2==0 and f == 1:
        f = 0
        continue
    if f == 0 and (s1+s2) == 0:
        continue
    if f == 2:
        s1 -= 1
        p+=1
        f = 1
    elif f == 1:
        s2 -= 1
        p+=1
        f = 2
    elif f == 0:
        if s1>s2:
            s1 -= 1
            p+=1
            f = 1
        else:
            s2-=1
            p+=1
            f= 2
            
print(p)


t = input().split(' ')
n = int(t[0])
a = int(t[1])
b = int(t[2])
s = input()
L = [0] * len(s)
for i in range(len(s)):
    if s[i] == '.':
        L[i] = 1
M = [0] + L + [0]
c = True
d = False
tot = 0
for j in range(1, len(s)+1):
    if M[j] == 1 and M[j-1] != 2 and a > 0:
        c = True
    else:
        c = False
    if M[j] == 1 and M[j-1] != 3 and b > 0:
        d = True
    else:
        d = False
    if c and d:
        if a > b:
            d = False
        else:
            c = False
    if c and not d:
        M[j] = 2
        a -= 1
        tot += 1
    if d and not c:
        M[j] = 3
        b -= 1
        tot += 1
print(tot)


n, a, b = map(int,input().split())
cnt = 0
ans = 0
for x in input():
    if x == '.':
        cnt = cnt+1
    else:
        tmp = cnt//2
        if a > b:
            ans = ans+min(a,cnt-tmp)+min(b,tmp)
            a = max(0,a-cnt+tmp)
            b = max(0,b-tmp)
        else:
            ans = ans+min(a,tmp)+min(b,cnt-tmp)
            a = max(0,a-tmp)
            b = max(0,b-cnt+tmp)
        cnt = 0
tmp = cnt//2
if a > b:
    ans = ans+min(a,cnt-tmp)+min(b,tmp)
    a = max(0,a-cnt+tmp)
    b = max(0,b-tmp)
else:
    ans = ans+min(a,tmp)+min(b,cnt-tmp)
    a = max(0,a-tmp)
    b = max(0,b-cnt+tmp)
print(ans)

n, a, b = list(map(int, input().split()))
s = list(map(len, input().split('*')))
a_, b_ = a, b

for i in s:
    x, y = i // 2, i // 2 + i % 2
    if a > b:
        a -= y
        b -= x
    else:
        a -= x
        b -= y

print((a_ - max(0, a)) + (b_ - max(0, b)))


n, a, b = list(map(int, input().strip().split()))
s = input().split('*')
rslt = 0
for segment in s:
    less = len(segment)//2
    more = len(segment) - less;
    x = 0
    y = 0
    if a > b:
        x = min(a, more)
        y = min(b, less)
    else:
        x = min(a, less)
        y = min(b, more)

    rslt += (x+y)
    a -= x
    b -= y
print(rslt)


a, b, c = list(map(int, input().split()))
b2 = b
c2 = c
d2 = input()
d = []
for i in range(len(d2)):
    d.append(d2[i])
k = 0
for i in range(len(d)):
    if d[i] == '.':
        if i > 0:
            if d[i - 1] == '*':
                if b < c:
                    d[i] = 2
                    c -= 1
                else:
                    d[i] = 1
                    b -= 1
            else:
                if d[i - 1] == 1:
                    d[i] = 2
                    c -= 1
                else:
                    d[i] = 1
                    b -= 1
        else:
            if b < c:
                d[i] = 2
                c -= 1
            else:
                d[i] = 1
                b -= 1
res = 0
if b >= 0:
    res += b2 - b
else:
    res += b2
if c >= 0:
    res += c2 - c
else:
    res += c2
print(res)      

n,a,b=[int(x) for x in input().split()]
all=a+b
#print(all)
s=input()
#print(s)
l=0
ls=[]
for c in s:
    if c=='*':
        if l!=0:
            ls.append(l)
            l=0
    else:
        l+=1
if l!=0:
    ls.append(l)

def rem(room,a,b):
    if room%2==0:
        return a-room//2,b-room//2
    if room%2++1:
        if a>b:
            return a-(room-1)//2-1,b-(room-1)//2
        else:
            return a - (room - 1) // 2, b - (room - 1) // 2 - 1

for ll in ls:
    a,b=rem(ll,a,b)
if a>0:
    all-=a
if b>0:
    all-=b

print(int(all))

n,a,b=list(map(int,input().split()))
inp=input().split("*")
L=[]
for i in inp:
    L.append(len(i))

out=0
for i in L:
    c1=i//2
    c2=i-c1
    if b<a:
        a,b=b,a
    if a<c1:
        out+=a
        a=0
    else:
        a-=c1
        out+=c1
    if b<c2:
        out+=b
        b=0
    else:
        b-=c2
        out+=c2
print(out)
    
        
    


#!/usr/bin/env python3

[n, a, b] = list(map(int, input().strip().split()))
s = input().strip() + '*'

l0 = 0  # tot len of even parts
n1 = 0  # num of odd parts

i_prev = -1
while True:
	i_next = s.find('*', i_prev + 1)
	if i_next < 0:
		break
	l = i_next - i_prev - 1
	l0 += l // 2
	n1 += l % 2
	i_prev = i_next

c = min(a, b, l0)
res = 2 * c
a -= c
b -= c
l0 -= c
res += min(l0 + n1, a + b)

print (res)