Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
field=[[float('inf') for i in range(w)] for j in range(h)]

q=deque()

for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
            field[i][j]=0

dx=[1,0,-1,0]            
dy=[0,1,0,-1]
ans=0

while q:
    y,x=q.popleft()    
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<h and 0<=nx<w and field[ny][nx]==float('inf'):
            field[ny][nx]=field[y][x]+1
            q.append((ny,nx))
            ans=max(ans,field[ny][nx])
print(ans)

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
field=[[False for i in range(w)] for j in range(h)]
 
q=deque()
 
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
            field[i][j]=True
 
dx=[1,0,-1,0]            
dy=[0,1,0,-1]
ans=0
 
while q:
    nq=deque()
    while True:
        y,x=q.popleft()    
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<h and 0<=nx<w and field[ny][nx]==False:
                field[ny][nx]=True
                nq.append((ny,nx))

        if not q:
            ans+=1
            q=nq
            break
print(ans-1)
### BUGGY CODE ###

from bisect import bisect

n = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(n):
	for j in range(i+1, n):
		for k in range(j+1, bisect(L, L[i]+L[j]-1)):
			if k != i and k != j:
				ans+=1
print(ans)

### FIXED CODE ###

from bisect import bisect

n = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(n):
	for j in range(i+1, n):
		ans+=bisect(L, L[i]+L[j]-1)-j-1
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())

query_list = []
for _ in range(q):
    query_list += [input()]


def query1(s):
    s = s[::-1]
    return s

def query2_1(letters,s):
    s = letters[4] + s
    return s

def query2_2(letters,s):
    s = s +  letters[4]
    return s

for i in range(q):
    if len(query_list[i])==1:
        s = query1(s)
        # print(s)
    else:
        if query_list[i][2]=="1":
            s = query2_1(query_list[i],s)
            # print(s)
        elif query_list[i][2]=="2":
            s = query2_2(query_list[i],s)
            # print(s)

print(s)

### FIXED CODE ###

s = input()
q = int(input())

query_list = []
for _ in range(q):
    query_list += [input()]


def query1(s):
    s = s[::-1]
    return s

def query2_1(letters,s):
    s = letters[4] + s
    return s

def query2_2(letters,s):
    s = s +  letters[4]
    return s

true_position = True
left = ""
right = ""

for i in range(q):
    if len(query_list[i])==1:
        true_position = not true_position
        # print(s)
    else:
        if query_list[i][2]=="1":
            if true_position:
                left = query_list[i][4] + left
            else:
                right = right + query_list[i][4]
        elif query_list[i][2]=="2":
            if true_position:
                right = right + query_list[i][4]
            else:
                left = query_list[i][4] + left

if true_position:
    ans = left + s + right
else:
    ans = right[::-1]+s[::-1]+left[::-1]

print(ans)
### BUGGY CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    s=input()
    k=int(input())
    ans=0
    
#    print(x)
    if s[0]!=s[-1]:
        y=[len(list(v))//2 for k,v in groupby(s)]
        print(sum(y)*k)
    else:
        while 1:
            print()
        x=[len(list(v))//2 for k,v in groupby(s)]
        #print(x)
        if len(x)!=1:
            ans+=x[0]+x[-1]
#            print(ans)
            ans+=sum(x[1:-1])*k
#            print(ans)
            ans+=(k-1)*(x[0]+x[-1])
            print(ans)
        else:
            print(len(s)*k//2)
        
    


if __name__ == '__main__':
    main()

### FIXED CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    s=input()
    k=int(input())
    ans=0
    n=[len(list(v)) for k,v in groupby(s)]
#    print(x)
    if s[0]!=s[-1]:
        y=[len(list(v))//2 for k,v in groupby(s)]
        print(sum(y)*k)
    else:
        x=[len(list(v))//2 for k,v in groupby(s)]
#        print(x)
        if len(x)!=1:
            ans+=x[0]+x[-1]
#            print(ans)
            ans+=sum(x[1:-1])*k
#            print(ans)
            ans+=(k-1)*((n[0]+n[-1])//2)
            print(ans)
        else:
            print(len(s)*k//2)
        
    


if __name__ == '__main__':
    main()
### BUGGY CODE ###

x, y, z, K = map(int, input().split())
A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)


def check(P):
    cnt = 0
    for i in range(x):
        for j in range(y):
            for k in range(z):
                if A[i]+B[j]+C[k] < P:
                    break
                cnt += 1
                if K <= cnt:
                    return True
    return False


L = 1
R = 10**14
while L != R-1:
    M = (L+R)//2
    if check(M):
        L = M
    else:
        R = M

ans = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if A[i]+B[j]+C[k] < L:
                break
            ans.append(A[i]+B[j]+C[k])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])


### FIXED CODE ###

from itertools import product
x, y, z, k = map(int, input().split())
A = map(int, input().split())
B = map(int, input().split())
C = map(int, input().split())
AB = [sum(ab) for ab in product(A, B)]
AB.sort(reverse=True)
AB = AB[:k]
ABC = [sum(abc) for abc in product(AB, C)]
ABC.sort(reverse=True)
for i in range(k):
    print(ABC[i])
### BUGGY CODE ###

N=int(input())
S=input()
ans=S.count("R")*S.count("G")*S.count("B")
for i in range(0,N-2):
    for j in range(i+1,N-1):
        try:
            if S[i]!=S[j] and S[j]!=S[2*j-i] and S[i]!=S[2*j-i]:
                ans-=1
        except:
            continue
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
ans=S.count("R")*S.count("G")*S.count("B")
for i in range(0,N-2):
    for j in range(i+1,N-1):
        if 2*j-i<N:
            if S[i]!=S[j] and S[j]!=S[2*j-i] and S[i]!=S[2*j-i]:
                ans-=1
print(ans)
### BUGGY CODE ###

s=input()
dp=[[0]*13 for _ in range(10**5+5)]
dp[0][0]=1
for i in range(len(s)):
    if s[i]=='?':
        c=-1
    else:
        c=int(s[i])
    
    for j in range(10):
        if c!=-1 and c!=j:
            continue
        for k in range(13):
            dp[i+1][(k*10+j)%13]+=dp[i][k]
    for j in range(13):
        dp[i+1][j]%=(10**9+7)

print(dp[len(s)][5])

### FIXED CODE ###

s=input()
dp=[[0]*13 for _ in range(len(s)+5)]
dp[0][0]=1
for i in range(len(s)):
    
    if s[i]!='?':  
        j=int(s[i])
        for k in range(13):
            dp[i+1][(k*10+j)%13]+=dp[i][k]
            dp[i+1][(k*10+j)%13]%=(10**9+7)
    else:
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13]+=dp[i][k]
                dp[i+1][(k*10+j)%13]%=(10**9+7)

print(dp[len(s)][5])
### BUGGY CODE ###

from sys import stdin
import numpy as np
from scipy.ndimage.filters import minimum_filter, maximum_filter

def init_maze(maze, H, W, start, goal):
    cost = np.zeros((H, W), dtype=int) + 999
    done = np.zeros((H, W), dtype=bool)
    barrier = np.zeros((H, W), dtype=bool)
    for i in range(H):
        for j in range(W):
            if (i, j) == start:
                # start = (i, j)
                cost[i, j] = 0
                done[i, j] = True
            if (i, j) == goal:
                pass
                # goal = (i, j)
            if maze[i][j] == '#':
                barrier[i,j] = True
    return cost, done, barrier

def bnf(maze, cost, done, barrier, goal, g):
    for i in range(1, 999):
        done_next = maximum_filter(done, footprint=g) * ~done

        cost_next = minimum_filter(cost, footprint=g) * done_next
        cost_next[done_next] += 1

        cost[done_next] = cost_next[done_next]
        cost[barrier] = 999

        done[done_next] = done_next[done_next]
        done[barrier] = False

        if done[goal[0], goal[1]] == True:
            return max(cost_next[done_next])
            break
    return 0


if __name__ == '__main__':
    H, W = [ int(x) for x in stdin.readline().rstrip().split() ]
    maze = []
    for i in range(H):
        maze.append(stdin.readline().rstrip())

    index = []
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '.':
                index.append((i, j))

    g = np.array([
        [0,1,0],
        [1,1,1],
        [0,1,0]
    ])

    costs = []
    for idx_start in index:
        start = idx_start
        for idx_goal in index:
            goal = idx_goal
            cost, done, barrier = init_maze(maze, H, W, start, goal)
            cost, done, barrier = init_maze(maze, H, W, start, goal)
            costs.append(bnf(maze, cost, done, barrier, goal, g))
    print(max(costs))


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

from collections import deque

H, W = input_nums()
H += 2
W += 2
grid = '#' * W
for i in range(H - 2):
    grid += '#' + input() + '#'
grid += '#' * W

def bfs(start):
    INF = 10**9
    dist = [INF] * (H * W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (1, -1, W, -W):
            next_v = v + move
            if grid[next_v] == '#':
                continue
            d_next_v = dv + 1
            if d_next_v >= dist[next_v]:
                continue
            dist[next_v] = d_next_v
            q.append(next_v)
    return max([x for x in dist if x < INF])

ans = max([bfs(x) for x in range(H * W) if grid[x] != '#'])
print(ans)
### BUGGY CODE ###


N = int(input())
A=list(map(int,input().split()))
ans=1

for i in range(N):
    ans *= A[i]

if(ans>1000000000000000000):
    print("-1")
else:
    print(ans)
    




### FIXED CODE ###

N = int(input())
A=list(map(int,input().split()))
ans=1
flag=0

for i in range(N):
    if(A[i]==0):
        flag=1

if flag==0:        
    if(N%2==0):
        for i in range(int(N/2)):
            ans *= (A[i]*A[N-1-i])
            if(ans>1000000000000000000):
              break
    else:
        for i in range(int(N/2)):
            ans *= A[i]*A[N-1-i]
            if(ans>1000000000000000000):
                break
        ans*=A[int((N-1)/2)]

if flag==1:
    print(0)
elif(ans>1000000000000000000):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

T=[[0,0,[-1]*26]]
N=int(input())
S=[[ord(C)-97 for C in input()]for _ in[0]*N]
for X in S:
    P=0
    for C in X:
        if T[P][2][C]<0:
            T[P][2][C]=len(T)
            T+=[[0,0,[-1]*26]]
        T[P][0]+=1
        P=T[P][2][C]
    T[P][0]+=1
    T[P][1]=1
U=N*26**2*[0]
V=N*[0]
for I in range(N):
    P=0
    for C in S[I]:
        for A in range(26):
            X=T[P][2][A]
            if X>=0 and A!=C:
                U[676*I+26*A+C]+=T[X][0]
        V[I]+=T[P][1]
        P=T[P][2][C]
Q=int(input())
for I in range(Q):
    K,P=input().split()
    K=int(K)-1
    P=[ord(C)-97 for C in P]
    X=1+V[K]
    for A in range(26):
        for B in range(A+1,26):
            X+=U[676*K+26*P[A]+P[B]]
    print(X)

### FIXED CODE ###

from array import*;R=range;T=[0]*28;N=int(input());S=[[ord(C)-95 for C in input()]for _ in[0]*N];U=N*26**2*array('i',[0]);V=N*[0];Q=int(input())
for X in S:
	P=0
	for C in X:
		if T[P+C]==0:T[P+C]=len(T);T+=[0]*28
		T[P]+=1;P=T[P+C]
	T[P]+=1;T[P+1]=1
for I in R(N):
	P=0
	for C in S[I]:
		for A in R(26):
			X=T[P+A+2]
			if(A!=C-2)*X:U[676*I+26*A+C-2]+=T[X]
		V[I]+=T[P+1]
		P=T[P+C]
while Q:
	K,P=input().split();K=int(K)-1;P=[ord(C)-97 for C in P];X=1+V[K]
	for A in R(26):
		for B in R(A+1,26):
			X+=U[676*K+26*P[A]+P[B]]
	print(X);Q-=1
### BUGGY CODE ###

N, K = map(int, input().split())

if K == 1:
    print(0)
    quit()

pre = N
new = abs(N - K)
while new < pre:
    #print(pre, new)
    pre = new
    new = abs(new - K)
print(pre)

### FIXED CODE ###

N, K = map(int, input().split())
import math
if N > K:
    s = N // K
    print(min(abs(N - s * K), abs(N - (s + 1) * K)))
elif N == K:
    print(0)
else:
    print(min(N, abs(N - K)))
### BUGGY CODE ###

n=int(input())
s=[]
ans=set()
for _ in range(n):
    s.append(str(input()))
count=[0]*len(set(s))
for i in range(len(set(s))):
    for j in range(len(s)):
        if list(set(s))[i]==s[j]:
            count[i]+=1
for k in range(len(set(s))):
    if max(count)==count[k]:
        ans.add(list(set(s))[k])
for l in range(len(ans)):
    print(sorted(ans)[l])

### FIXED CODE ###

import collections
n=int(input())
s=[]
for _ in range(n):
    s.append(str(input()))
ans=collections.Counter(s)
a=max(ans.values())
ans=[i for i,k in ans.items() if a==k]
print(*sorted(ans),sep="\n")
### BUGGY CODE ###

import functools
import operator

N = int(input())
A = [int(i) for i in input().split()]

Π = functools.partial(functools.reduce, operator.mul)
if Π(A) > 10 ** 18:
    print(-1)
else:
    print(Π(A))

'''

if len(A) == 2:
    ans = A[0] * A[1]
    if ans > 10 ** 18:
        print(-1)
    else:
        print(ans)
else:
    ans = np.prod(A)
    if ans > 10 ** 18:
        print(-1)
    else:
        print(ans)
'''


### FIXED CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

a = k()
b = l()
b.sort()
ans = 1
for i in b:
    if i == 0:
        print(0)
        sys.exit()
    else:
        ans *= i
    if ans > 10**18:
        print(-1)
        sys.exit()

print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [''.join(str(bin(x)).replace('0b', '')).zfill(60) for x in a]

ans = 0
for i in range(60):
    n0 = 0
    n1 = 0
    for j in a:
        if j[i] == '0':
            n0+=1
        else:
            n1+=1
    ans+=((2**(60-i-1)) * n0 * n1)
    
print(ans%(10**9 + 7))

### FIXED CODE ###

N = int(input())
A = [str(bin(a)).lstrip('0b').zfill(60) for a in map(int,input().split())]
A_rev = list(zip(*A))

ans = 0
for i, a in enumerate(A_rev):
	k = a.count('1')
	ans+=(k*(N-k)*2**(59-i))
print(ans%(10**9+7))
### BUGGY CODE ###

from collections import defaultdict,deque
import sys
N=int(input())
G=defaultdict(list)
for i in range(N-1):
  x,y,d=map(int,input().split())
  G[x].append((y,d))
  G[y].append((x,d))
Q,K=map(int,input().split())
stack=deque()
stack.append(K)
seen=[]
dist=[float('inf')]*N
dist[K-1]=0
while stack:
  u=stack.pop()
  seen.append(u)
  for v,d in G[u]:
    if v not in seen:
      dist[v-1]=min(dist[v-1],dist[u-1]+d)
      stack.append(v)
for q in range(Q):
  x,y=map(int,input().split())
  print(dist[x-1]+dist[y-1])

### FIXED CODE ###

N=int(input())
G=[[] for _ in range(N)]
for i in range(N-1):
  x,y,d=map(int,input().split())
  x-=1
  y-=1
  G[x].append((y,d))
  G[y].append((x,d))
Q,K=map(int,input().split())
stack=[K-1]
unseen=[1]*N
dist=[float('inf')]*N
dist[K-1]=0
while stack:
  u=stack.pop()
  unseen[u]=0
  for v,d in G[u]:
    if unseen[v]:
      dist[v]=min(dist[v],dist[u]+d)
      stack.append(v)
for q in range(Q):
  x,y=map(int,input().split())
  print(dist[x-1]+dist[y-1])
### BUGGY CODE ###

k = int(input())
memo = [[-1 for i in range(k+1)] for j in range(k+1)]
def gcd(a, b):
    if b == 0:
        return a
    else:
        if memo[a][b] == -1:
            memo[a][b] = gcd(b, a % b)
        return memo[a][b]
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(gcd(a,b), c)

print(ans)

### FIXED CODE ###

k = int(input())
memo = [[-1 for i in range(k+1)] for j in range(k+1)]
def gcd(a, b):
    if b == 0:
        return a
    else:
        if memo[a][b] == -1:
            memo[a][b] = gcd(b, a % b)
        return memo[a][b]
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(gcd(a,b), c)

print(ans)
### BUGGY CODE ###

import collections
def main():
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(input())

    rows = []
    rows_val = dict()
    id = 0
    for i in range(H):
        count = 0
        temp = []
        id += 1
        for j in range(W):
            if grid[i][j] == "#":
                if count > 0:
                    rows_val[id] = count
                count = 0
                id += 1
                temp.append(None)
            else:
                temp.append(id)
                count += 1
        if count > 0:
            rows_val[id] = count
        rows.append(temp)
    # print(rows)

    cols = []
    cols_val = dict()
    id = 0
    for j in range(W):
        count = 0
        temp = []
        id += 1
        for i in range(H):
            if grid[i][j] == "#":
                if count > 0:
                    cols_val[id] = count
                count = 0
                id += 1
                temp.append(None)
            else:
                count += 1
                temp.append(id)
        if count > 0:
            cols_val[id] = count
        cols.append(temp)

    max_v = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == ".":
                v = rows_val[rows[i][j]]
                v += cols_val[cols[j][i]] - 1 # -1 for overlap
                max_v = max(max_v, v)
    return max_v


if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import collections
def main():
    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(input())

    rows = []
    rows_val = dict()
    id = 0
    for i in range(H):
        count = 0
        temp = []
        id += 1
        for j in range(W):
            if grid[i][j] == "#":
                if count > 0:
                    rows_val[id] = count
                count = 0
                id += 1
                temp.append(None)
            else:
                temp.append(id)
                count += 1
        if count > 0:
            rows_val[id] = count
        rows.append(temp)
    # print(rows)

    cols = []
    cols_val = dict()
    id = 0
    for j in range(W):
        count = 0
        temp = []
        id += 1
        for i in range(H):
            if grid[i][j] == "#":
                if count > 0:
                    cols_val[id] = count
                count = 0
                id += 1
                temp.append(None)
            else:
                count += 1
                temp.append(id)
        if count > 0:
            cols_val[id] = count
        cols.append(temp)

    max_v = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == ".":
                v = rows_val[rows[i][j]]
                v += cols_val[cols[j][i]] - 1 # -1 for overlap
                max_v = max(max_v, v)
    return max_v


if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

s = int(input())

x1, y1 = 0, 0
x2, y2, x3, y3 = 0, 0, 0, 0

while True:
    if s >= 10e14:
        for i in range(min(int(s**0.5), 10e9), 0, -1):
            if s % i == 0 and i <= 10e9 and s / i <= 10e9:
                x2 = i
                y3 = s//i
                break
    else:
        for i in range(1, min(int(s**0.5), 10e9) + 1):
            if s % i == 0 and i <= 10e9 and s / i <= 10e9:
                x2 = i - x1
                y3 = s//i
                break

    if x2 == 0 and y3 == 0:
        y2 = -1
        x3 += 1
        s -= x3
        continue
    break

print(x1, y1, x2, y2, x3, y3)


### FIXED CODE ###

s = int(input())

e = 10**9
if s == e**2:
    print(0, 0, e, 1, 0, e)
else:
    y = s//e + 1
    x = y*e - s
    print(0, 0, e, 1, x, y)
### BUGGY CODE ###

from collections import Counter

N = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)

ansers = dict()
for i in range(N):
    print(sum(v*(v-1)//2 if A[i]!=k else (v-1)*(v-2)//2 for k, v in C.items()))


### FIXED CODE ###

from collections import Counter

N = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)

MX = sum(v*(v-1) for v in C.values())//2
for i in range(N):
    print(MX-C[A[i]]+1)
### BUGGY CODE ###

N, K = map(int, input().split())
S = input()

S += '2'
l = []
cnt = 1
for i in range(N):
  if S[i] == S[i+1]:
  	cnt += 1
  else:
    l.append(cnt)
    cnt = 1

if S[0] == '0':
  ans = sum(l[:2*K])
  for j in range(1, len(l), 2):
    ans = max(ans, sum(l[j: j+2*K+1]))
else:
  ans = 0
  for j in range(0, len(l), 2):
    ans = max(ans, sum(l[j: j+2*K+1]))
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
S = input()

S += '2'
l = []
cnt = 1
for i in range(N):
  if S[i] == S[i+1]:
  	cnt += 1
  else:
    l.append(cnt)
    cnt = 1

if S[0] == '0':
  cur = sum(l[:2*K])
  ans = cur
  for j in range(1, len(l), 2):
    cur += -sum(l[max(0, j-2): j]) + sum(l[j+2*K-1:j+2*K+1])
    ans = max(ans, cur)
else:
  cur = sum(l[:2*K+1])
  ans = cur
  for j in range(2, len(l), 2):
    cur += -sum(l[max(0, j-2): j]) + sum(l[j+2*K-1:j+2*K+1])
    ans = max(ans, cur)
print(ans)
### BUGGY CODE ###

k,s=map(int,input().split())

ans=0
for i in range(k+1):
    for j in range(k+1):
        for h in range(k+1):
            if(i+j+h==s):
                ans+=1

print(ans)

### FIXED CODE ###

k,s=map(int,input().split())

ans=0
for i in range(k+1):
    for j in range(k+1):
        if(0<=s-i-j<=k):
            ans+=1

print(ans)
### BUGGY CODE ###

"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_i

I - Coins

"""
import collections


def solve(ps):
    dp = collections.defaultdict(float)
    dp[0] = 1.0
    for p_i in ps:
        for head_count in reversed(range(N + 1)):
            dp[head_count] = p_i * dp[head_count - 1] + (1 - p_i) * dp[head_count]

    more_than_half = (N + 2) // 2
    res = sum(dp[head_count] for head_count in range(more_than_half, N + 1))
    return res
 

N = int(input())
ps = [float(s) for s in input().split()]
res = solve(ps)
print(res)


### FIXED CODE ###

"""
AtCoder Educational DP Contest
https://atcoder.jp/contests/dp/tasks/dp_i

I - Coins

"""
import collections


def solve(ps):
    dp = collections.defaultdict(float)
    dp[0] = 1.0
    for p_i in ps:
        for head_count in reversed(range(N + 1)):
            dp[head_count] = p_i * dp[head_count - 1] + (1 - p_i) * dp[head_count]

    more_than_half = (N + 2) // 2
    res = sum(dp[head_count] for head_count in range(more_than_half, N + 1))
    return res
 

N = int(input())
ps = [float(s) for s in input().split()]
res = solve(ps)
print(res)