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

s = input()
ans = 0

for i in range(2*10**5):
    ss = s.count('BW')
    if ss == 0:
        break
    ans += ss
    s = s.replace('BW', 'WB')
print(ans)

### FIXED CODE ###

s = input()
ans = 0
ss = s.count('B')
sss = len(s)
index = -1
sum_s = 0

for i in range(ss):
    index = s.find('B', index+1)
    ans += sss-index-1
    sum_s += i
    
ans -= sum_s
print(ans)
### BUGGY CODE ###

A,B,M=map(int,input().split())

m=[[0] * B for i in range(A)]

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

minc=min(a)+min(b)

for i in range(M):
  x,y,c=map(int,input().split())
  cash=a[x-1]+b[y-1]-c

  if cash<minc:
    minc=cash


print(minc)

### FIXED CODE ###

A,B,M=map(int,input().split())

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

minc=min(a)+min(b)

for i in range(M):
  x,y,c=map(int,input().split())
  cash=a[x-1]+b[y-1]-c

  if cash<minc:
    minc=cash

print(minc)
### BUGGY CODE ###

A,B,C,D = map(int,input().split())
while True:
    C -= B
    A -= D
    if C == 0:
        print ("Yes")
        break
    if A == 0: 
        print ("No")
        break

### FIXED CODE ###

A,B,C,D = map(int, input().split())
Takahashi=0
Aoki=0
while C-B>0:
    C-=B
    Takahashi+=1
while A-D>0:
    A-=D
    Aoki+=1
print("Yes") if Aoki>=Takahashi else print("No")
### BUGGY CODE ###

n = int(input())
x = map(int, input().split())
x = list(x)
for c in x:
    x_remove = x.copy()
    x_remove.remove(c)
    x_remove.insert(0,0)
    x_remove.append(0)
    i = 0
    ans = 0
    for i, b in enumerate(x_remove[1:]):
        ans += abs(x_remove[i] - b)        
        i += 1
    print(ans)

### FIXED CODE ###

n = int(input())
X = map(int, input().split())
X = list(X)
# n = 3
# X = [3, 5, -1]

X.insert(0,0)
X.append(0)
Y = []
for i, x in enumerate(X[1:]):
    Y.append(abs(x-X[i]))
sumY = sum(Y)

for i, x in enumerate(X):
    if i not in [0,len(X)-1]:
        ans = sumY - (Y[i-1] + Y[i]) + abs(X[i+1]-X[i-1])
        print(ans)
### BUGGY CODE ###

def rabin_karp(T, P, d, q):
    n = len(T)
    m = len(P)
    if n < m:
        return
    h = 1
    p = 0
    t0 = 0
    for _ in range(m - 1):
        h = int((h * d) % q)
    for i in range(m):
        p = int((d * p + P[i]) % q)
        t0 = int((d * t0 + T[i]) % q)
    # print("h = ", h)
    # print("p = ", p)
    for s in range(n - m + 1):
        # print("t0 = ", t0)
        if p == t0:
            for i in range(m):
                if P[i] != T[s + i]:
                    # print(i, s+i)
                    break
                if i == m - 1:
                    print(s)
        if s < n - m:
            # print("     ", t0 - T[s] * h)
            # print("     ",  d)
            # print("     ", T[s + m])
            t0 = int((d * (t0 - T[s] * h) + T[s + m]) % q)


d = 999999937
q = 1000000007
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d, q)


### FIXED CODE ###

def compute_prefix_function(p):
    m = len(p)
    pi = [0 for _ in range(m + 1)]
    pi[1] = 0
    k = 0
    for q in range(2, m + 1):
        while k > 0 and p[k] != p[q - 1]:
            k = pi[k]
        if p[k] == p[q - 1]:
            k += 1
        pi[q] = k
    return pi


def kmp_matcher(t, p):
    n = len(t)
    m = len(p)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(1, n + 1):
        while q > 0 and p[q] != t[i - 1]:
            q = pi[q]
        if p[q] == t[i - 1]:
            q += 1
        if q == m:
            print(i - m)
            q = pi[q]


t = input()
p = input()
kmp_matcher(t, p)
### BUGGY CODE ###

N = int(input())
S = input()

cnt = float('inf')
for i in range(N):
    W = S[:i].count('W')
    E = S[i + 1:].count('E')
    cnt = min(E + W, cnt)
    
print(cnt)

### FIXED CODE ###

N = int(input())
S = input()

cnt = [[0, 0] for _ in range(N)]

if S[0] == 'W':
    cnt[0][0] = 1

if S[-1] == 'E':
    cnt[-1][1] = 1

for i in range(1, N):
    cnt[i][0] += cnt[i - 1][0]
    if S[i] == 'W':
        cnt[i][0] += 1
    
for i in range(N - 2, -1, -1):
    cnt[i][1] += cnt[i + 1][1]
    if S[i] == 'E':
        cnt[i][1] += 1

count = float('inf')
for i in range(N):
    count = min(count, cnt[i][0] + cnt[i][1])

print(count - 1)
### BUGGY CODE ###

def calc():
  n=int(input())
  arr=list(map(int,input().split()))
  acum1=[0]
  acum2=[0]
  for i in range(n):
    if i%2==0:
      acum1.append(acum1[-1]+arr[i])
      acum2.append(acum2[-1]+0)
    else:
      acum1.append(acum1[-1]+0)
      acum2.append(acum2[-1]+arr[i])
  if n%2==0:
    ans=max(acum1[n-1],acum2[n])
    for i in range(1,n+1,2):
      if i+3>n:
        continue
      tmp=(acum1[i]-acum1[0])+(acum2[n]-acum2[i+2])
      ans=max(ans,tmp)
  else:
    ans=max(acum1[n-2]-acum1[0],acum2[n-1]-acum2[1],acum1[n]-acum1[2])
    for i in range(1,n+1,2):
      if i+3>n-1:
        continue
      tmp=(acum1[i]-acum1[0])+(acum2[n-1]-acum2[i+2])
      ans=max(ans,tmp)
    for i in range(2,n+1,2):
      if i+3>n:
        continue
      tmp=(acum2[i]-acum2[1])+(acum1[n]-acum1[i+2])
      ans=max(ans,tmp)
    for i in range(1,n+1,2):
      if i+4>n:
        continue
      tmp=(acum1[i]-acum1[0])+(acum1[n]-acum1[i+3])
      ans=max(ans,tmp)
    for i in range(1,n+1,2):
      for j in range(i+3,n+1,2):
        if j+3>n:
          continue
        tmp=(acum1[i]-acum1[0]-acum2[i+2])+(acum2[j]+acum1[n]-acum1[j+2])
        ans=max(ans,tmp)
  print(ans)
calc()

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
if n<=3:
  print(max(arr))
  exit()
lim=n%2+2
dp=[[0]*lim for _ in range(n+1)]
for i in range(n):
  dp[i+1][0]=dp[i-1][0]+arr[i]
  dp[i+1][1]=max(dp[i-1][1]+arr[i],dp[i-2][0]+arr[i])
  if lim==3:
    dp[i+1][2]=max(dp[i-1][2]+arr[i],dp[i-2][1]+arr[i],dp[i-3][0]+arr[i])
print(max(dp[-1][:lim]))
### BUGGY CODE ###

from sys import stdin
import bisect

def knapsack(N,W,w,v):
    dp=[[0 for i in range(W+1)]for j in range(N+1)]
    for i in range(N):
        for j in range(W+1):
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
            next_w=j+w[i]
            next_v=dp[i][j]+v[i]
            if(next_w<=W and next_v>dp[i+1][next_w]):
                dp[i+1][next_w]=next_v
    ans = 0
    for i in range(W+1):
        ans=max(ans,dp[N][i])
    return(ans)

N,W = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(N)]

v = []
w = []

for i in range(N):
    v.append(li[i][0])
    w.append(li[i][1])

print(knapsack(N,W,v,w))

### FIXED CODE ###

from sys import stdin
n,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
def knapsack(n,w,li):
    #li[i][0]が重さ,li[i][1]が価値
    dp = [[0 for i in range(w+1)]for j in range(n+1)]
    #dp[i][total_w]はi-1回目までの商品を加えた時に重さがtotal_wを超えないような値の最大値
    for i in range(n):
        for total_w in range(w+1):
            if total_w - li[i][0] >= 0:
                dp[i+1][total_w] = max(dp[i][total_w],dp[i][total_w-li[i][0]]+li[i][1])
            else:
                dp[i+1][total_w] = dp[i][total_w]
    return max(dp[-1])
print(knapsack(n,w,li))
### BUGGY CODE ###

N,Q = [int(i) for i in input().split()]
S = input()

ans = []
for _ in range(Q):
    a,b = [int(i) for i in input().split()]
    ans.append(S[a-1:b].count('AC'))

for i in ans:
    print(i)


### FIXED CODE ###

import itertools
N,Q = [int(i) for i in input().split()]
S = list(input())

li = [0]*N
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        li[i+1] = 1
ans = list(itertools.accumulate(li))
k = []
for j in range(Q):
    a,b = [int(i) for i in input().split()]
    k.append(ans[b-1]-ans[a-1])

[print(i) for i in k]
### BUGGY CODE ###

n = int(input())
z = [list(map(int, input().split())) for i in range(n)]
d = [max(z[i][0] - z[j][0], z[j][0] - z[i][0]) + max(z[i][1] - z[j][1], z[j][1] - z[i][1]) for i in range(n-1) for j in range(i+1, n)]
print(max(d))
	


### FIXED CODE ###

n = int(input())
u = [list(map(int, input().split())) for i in range(n)]
z = [u[i][0] + u[i][1] for i in range(n)]
w = [u[i][0] - u[i][1] for i in range(n)]
d = [max(z)-min(z), max(w)-min(w)]

print(max(d))
### BUGGY CODE ###

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

dp = [[[0]*(2501) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 1

# i 個目までのj個選んで　和のmod aが k

for i in range(n):    
    for j in range(i+1):
        for k in range(2501):

            dp[i+1][j][k] += dp[i][j][k]
            if k+l[i] < 2501:
                dp[i+1][j+1][k+l[i]] += dp[i][j][k]


ans = 0
for j in range(1,n+1):
    ans += dp[-1][j][j*a]
print(ans)


### FIXED CODE ###

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

dp = [[[0]*(2501) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 1



for i in range(n):    
    for j in range(i+1):
        for k in range(2501):

            dp[i+1][j][k] += dp[i][j][k]
            if k+l[i] < 2501:
                dp[i+1][j+1][k+l[i]] += dp[i][j][k]


ans = 0
for j in range(1,n+1):
    ans += dp[-1][j][j*a]
print(ans)
### BUGGY CODE ###

from math import gcd
K=int(input())+1
sum=0
for a in range(1,K):
    for b in range(1,K):
        for c in range(1,K):
            AB = gcd(a,b)
            BC = gcd(b,c)
            ABC = gcd(AB,BC)
            sum = sum+ABC
print(sum)

### FIXED CODE ###

from math import gcd

K = int(input())
out = 0
Count = [0]*K
gcds = [[0]*K for i in range(K)]

for i in range (1,K+1):
    for j in range(1,+K+1):
        value = gcd(i,j)
        gcds[i-1][j-1]=value
        Count[value-1]+=1

for i in range(1,K+1):
    for j in range(1,K+1):
        out +=gcds[i-1][j-1]*Count[j-1] #値*回数
        
print(out)
### BUGGY CODE ###

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

plist = [i - 1 for i in map(int, input().split())]
slist = list(map(int, input().split()))
max_score = -math.inf
for start in range(N):
    total_score_in_loop = 0
    now = start
    score_loop = []
    while True:
        now = plist[now]
        total_score_in_loop += slist[now]
        score_loop.append(slist[now])
        if now == start:
            break
    score_rem = 0
    loop_score = 0
    for index, score in enumerate(score_loop, start=1):
        score_rem += score
        if total_score_in_loop > 0:
            loop_score = total_score_in_loop * ((K-index) // len(score_loop))
        max_score = max(max_score, score_rem+loop_score)
print(max_score)



### FIXED CODE ###

import numpy as np
from numba import njit

@njit('i8(i8,i8,i8[:],i8[:],i8)', cache=True)
def main(N, K, plist, slist, max_score):
    for start in range(N):

        total_score_in_loop = 0
        score_loop = []
        now = start
        while True:
            now = plist[now]
            total_score_in_loop += slist[now]
            score_loop.append(slist[now])
            if now == start:
                break
        
        rem_score, loop_score = 0, 0
        for idx in range(1, len(score_loop)+1):
            rem_score += score_loop[idx-1]
            if total_score_in_loop > 0:
                loop_score = ((K - idx) // len(score_loop)) * total_score_in_loop
            max_score = max(max_score, rem_score + loop_score)
    return max_score


N, K = map(int, input().split())
plist = np.array([i-1 for i in map(int, input().split())], dtype='int64')
slist = np.array([i for i in map(int, input().split())], dtype='int64')
max_score = -10**15
max_score = main(N, K, plist, slist, max_score)
print(max_score)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque

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

ans = [0 for _ in range(n)]

# 頂点'start'からBFS
def bfs(start):
    inf = 1001001001
    dist = [inf for _ in range(n)]
    q = deque()
    q.append(start)
    dist[start] = 0 

    def push(v, d): 
        if dist[v] != inf: return
        dist[v] = d 
        q.append(v)

    push(start, 0)
    while q:
        v = q.popleft()
        d = dist[v]
        if v-1 >= 0: push(v-1, d+1)
        if v+1 < n: push (v+1, d+1)
        if v==x: push(y, d+1)
        if v==y: push(x, d+1)
    
    for i in range(n):
        ans[dist[i]] += 1
    
for i in range(n):
    bfs(i)
for i in range(1, n): 
    print(ans[i]//2)


### FIXED CODE ###

#!/usr/bin/env python3
# TLE解
from collections import deque

n, x, y = map(int, input().split())
to = [[] for _ in range(n)]
for i in range(n):
    if i == 0:
        to[i].append(i+1)
    elif i == n-1:
        to[i].append(i-1)
    else:
        to[i].append(i+1) 
        to[n-i-1].append(n-i-2)
to[x-1].append(y-1)
to[y-1].append(x-1)

ans = [0 for _ in range(n)]

# 頂点'start'からBFS
def bfs(start):
    inf = 1001001001
    dist = [inf for _ in range(n)]
    q = deque()
    q.append(start)
    dist[start] = 0 

    while q:
        v = q.popleft()
        for u in to[v]:
            if dist[u] == inf:
                dist[u] = dist[v]+1
                q.append(u)
    # print('start = ', start, ': dist = ', dist)

    # for k in range(1, n):
    #     for i in range(n):
    #         if dist[i]-dist[start] == k:
    #             ans[k-1] += 1

    for i in range(n):
        ans[dist[i]] += 1
    
for i in range(n):
    bfs(i)
for i in range(1, n): 
    print(ans[i]//2)
### BUGGY CODE ###

from collections import *
from itertools import *
import copy

N,M,R=map(int,input().split())
Rlst=list(map(int,input().split()))
ABC=[list(map(int,input().split())) for i in range(M)]

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[0 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        stack=[[r1,0]]
        minpoint=[100000*200+1 for i in range(N+1)]
        while stack:
            a,m=stack.pop()
            for b in data[a]:
                A,B=min(a,b),max(a,b)
                tempm=m+nagasa[str(A)+" "+str(B)]
                if tempm<minpoint[b]:
                    minpoint[b]=tempm
                    if b==r2:
                        pass
                    else:
                        stack.append([b,tempm])
        mokutekiti[r1i][r2i]=minpoint[r2]
        mokutekiti[r2i][r1i]=minpoint[r2]

value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))


### FIXED CODE ###

from collections import *
from itertools import *
import copy
from heapq import *


N,M,R=map(int,input().split())
Rlst=list(map(int,input().split()))
ABC=[list(map(int,input().split())) for i in range(M)]

data=[[] for i in range(N+1)]
nagasa={}
for a,b,c in ABC:
    data[a].append(b)
    data[b].append(a)
    A,B=min(a,b),max(a,b)
    nagasa.update({str(A)+" "+str(B):c})
mokutekiti=[[100000*200+1 for i in range(R)] for m in range(R)]
for r1i in range(R-1):
    for r2i in range(r1i+1,R):
        r1=Rlst[r1i]
        r2=Rlst[r2i]
        visited=set()
        stack=[0]
        heapify(stack)
        dic={0:[r1]}
        while stack:
            m=heappop(stack)
            #if not m in visited:
            #visited.add(m)
            a=dic[m].pop()
            if not a in visited:
                visited.add(a)
                for b in data[a]:
                    if not b in visited or b==r2:
                        A,B=min(a,b),max(a,b)
                        tempm=m+nagasa[str(A)+" "+str(B)]
                        if b==r2:
                            if mokutekiti[r1i][r2i]>tempm:
                                mokutekiti[r1i][r2i]=tempm
                                mokutekiti[r2i][r1i]=tempm
                        else:
                            heappush(stack,tempm)
                            if tempm in dic:
                                dic[tempm].append(b)
                            else:
                                dic.update({tempm:[b]})



value=[]
for lst in permutations([i for i in range(R)],R):
    nagasa=0
    for i in range(R-1):
        nagasa+=mokutekiti[lst[i]][lst[i+1]]
    value.append(nagasa)
print(min(value))
### BUGGY CODE ###

n,ma,mb=map(int,input().split())
dp=[[0]*401 for _ in range(401)]
for _ in range(n):
  a,b,c=map(int,input().split())
  for i in range(400,-1,-1):
    for j in range(400,-1,-1):
      if i-a<0 or j-b<0:
        continue
      else:
        if dp[i-a][j-b]==0:
          continue
        else:
          if dp[i][j]==0:
            dp[i][j]=dp[i-a][j-b]+c
          else:
            dp[i][j]=min(dp[i][j],dp[i-a][j-b]+c)
  if dp[a][b]==0:
    dp[a][b]=c
  else:
    dp[a][b]=min(dp[a][b],c)
ans=10**10
for i in range(401):
  if i*ma>400 or i*mb>400:
    break
  if dp[i*ma][i*mb]==0:
    continue
  else:
    ans=min(ans,dp[i*ma][i*mb])
if ans==10**10:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

import sys



n, ma, mb = map(int, input().split())
abc = []

for _ in range(n):
    a, b, cost = map(int, input().split())
    abc.append((a, b, cost))

def main():
    sa = 0
    sb = 0
    for i in range(n):
        sa += abc[i][0]
        sb += abc[i][1]

    res = [[float('infinity')] * (sb + 1) for _ in range(sa + 1)]
    res[0][0] = 0

    for a, b, c in abc:

        for j in range(sa, -1, -1):
            for k in range(sb, -1, -1):
                if j >= a and k >= b:
                    res[j][k] = min(res[j][k], res[j-a][k-b] + c)

    ans = float('infinity')
    for i in range(1, min(sa//ma, sb//mb) + 1):
        ans = min(ans, res[ma*i][mb*i])

    if ans == float('infinity'):
        return -1
    else:
        return ans

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

import sys
sys.setrecursionlimit(10**9)

    
def g(to_li, from_li, dp, n):
    # nにつくパスの最大長
    if dp[n] != -1:
        return dp[n]
    if n == 0:
        return 0
    val = max([g(to_li, from_li, dp, t)+1 for t in to_li[n]])
    dp[n] = val
    return val
    

def main():
    N, M = [int(n) for n in input().split()]
    from_li = [[] for i in range(N+2)] # from[i]:=点iからつながった点
    to_li = [[] for i in range(N+2)] # to[i]:=点iにつながる点
    for i in range(M):
        x, y = [int(n) for n in input().split()]
        from_li[x].append(y)
        to_li[y].append(x)
    parents = []
    children = []
    dp = [-1]*(N+2)
    for index, to in enumerate(to_li):
        if len(to) == 0 and index != N+1 and index != 0:
            from_li[0].append(index)
            to_li[index].append(0)
    for index, fr in enumerate(from_li):
        if len(fr) == 0 and index != 0 and index != N+1:
            to_li[N+1].append(index)
            from_li[index].append(N+1)
    
    print(g(to_li, from_li, dp, N+1) - 2)




if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
def main():
    n, m = [int(n) for n in input().split()]
    paths = [[] for i in range(n+1)]
    for i in range(m):
        x, y = [int(r) for r in input().split()]
        paths[x].append(y)
    dp = [-1]*(n+1)

    ans = 0
    for i in range(n+1):
        ans = max(ans, dfs(paths, dp, i))
    print(ans-1)
def dfs(paths, dp, n):
    # nから下の最大長
    length = 0
    for p in paths[n]:
        val=0
        if dp[p] != -1:
            val = dp[p]
        else:
            val = dfs(paths, dp, p)
        length = max(length, val)
    length += 1 # pからnまでの一本もしくはnから終点までの一本
    dp[n] = length
    return length

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

class Node:
    def __init__(self, i):
        self.num = i
        self.goto = []
        self.kenken = set()

N, M = map(int, input().split())
nodes = [Node(i+1) for i in range(N)]

for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    nodes[v].goto.append(nodes[u])

s, t = map(int, input().split())
s -= 1
t -= 1

for i in range(N):
    for next in nodes[i].goto:
        for nextnext in next.goto:
            nodes[i].kenken = nodes[i].kenken | set(nextnext.goto)
    if nodes[i] in nodes[i].kenken:
        nodes[i].kenken.remove(nodes[i])

node = nodes[t]
step = 0
hist = [nodes[t].num]
check_list = [[node, step, hist]]
ok = False
while len(check_list) > 0:
    node, step, tmp = check_list.pop(0)
    hist = tmp
    if node == nodes[s]:
        print(step)
        ok = True
        break
    for next in node.kenken:
        if next.num not in hist:
            check_list.append([next, step+1, hist+[next.num]])
if not ok:
    print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
nodes = [[] for i in range(N)]

for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    nodes[u].append(v)

s, t = map(int, input().split())
s -= 1
t -= 1

num = s
step = 0
q = [[num, step]]
check = [[False for i in range(N)] for j in range(3)]
ok = False
while len(q) > 0:
    num, step = q.pop(0)
    tmp = step % 3
    if tmp == 0 and num == t:
        print(step//3)
        ok = True
        break
    for next in nodes[num]:
        if not check[tmp][next]:
            check[tmp][next] = True
            q.append([next, step+1])
if not ok:
    print(-1)
### BUGGY CODE ###

def solve():
    N = int(input())
    K = int(input())
    num = []
    dfs(0,0,num,N,K)
    print(len(num))

def dfs(now,cnt,lst,N,K):
    if now > N:
        return
    
    if cnt == K:
        lst.append(now)
    
    for i in range(10):
        next = now * 10 + i
        if i == 0:
            if now == 0:
                continue
            dfs(next,cnt,lst,N,K)
        else:
            dfs(next,cnt+1,lst,N,K)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    N = input()
    K = int(input())
    dp = [[[0]*(K+2) for i in range(2)] for j in range(len(N)+1)]
    dp[0][False][0] = 1

    for i in range(len(N)):
        for k in range(K+1):
            dp[i+1][True][k+1] += dp[i][True][k] * 9
            dp[i+1][True][k] += dp[i][True][k]

            if int(N[i]) > 0:
                dp[i+1][True][k+1] += dp[i][False][k] * (int(N[i]) - 1)
                dp[i+1][True][k] += dp[i][False][k]
            
            if int(N[i]) > 0:
                dp[i+1][False][k+1] = dp[i][0][k]
            else:
                dp[i+1][False][k] = dp[i][0][k]
    
    print(dp[-1][False][K] + dp[-1][True][K])

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

# coding: utf-8 
# Your code here! 
H,W=map(int,input().split()) 
S=[] 

ku=0
for _ in range(H): 
    S.append(list(input()))
    ku+=S[-1].count(".")


def bfs(h,w,num):
    if h==H-1 and w==W-1:
        print(ku-num-1)
        exit() 
    else:
        S[h][w]="#"

    if h!=0: 
        if S[h-1][w]!="#": 
            temp.append([h-1,w]) 

    if w!=0: 
        if S[h][w-1]!="#": 
            temp.append([h,w-1]) 

    if h!=H-1: 
        if S[h+1][w]!="#": 
            temp.append([h+1,w]) 

    if w!=W-1: 
        if S[h][w+1]!="#": 
            temp.append([h,w+1]) 
        
q=[[0,0]] 
count=-1
while True: 
    count+=1
    temp=[]
    while q:
        l=q.pop(0)
        bfs(l[0],l[1],count)
        
    q=temp[:]




    

### FIXED CODE ###

# coding: utf-8 
# Your code here! 
H,W=map(int,input().split()) 
S=[] 

ku=0
for _ in range(H): 
    S.append(list(input()))
    ku+=S[-1].count(".")


def bfs(h,w,num):
    if h==H-1 and w==W-1:
        print(ku-num-1)
        exit() 
    else:
        pass

    if h!=0: 
        if S[h-1][w]!="#": 
            temp.append([h-1,w])
            S[h-1][w]="#"

    if w!=0: 
        if S[h][w-1]!="#": 
            temp.append([h,w-1]) 
            S[h][w-1]="#"

    if h!=H-1: 
        if S[h+1][w]!="#": 
            temp.append([h+1,w]) 
            S[h+1][w]="#"

    if w!=W-1: 
        if S[h][w+1]!="#": 
            temp.append([h,w+1]) 
            S[h][w+1]="#"
        
q=[[0,0]] 
count=-1
while True: 
    count+=1
    #print(q)
    temp=[]
    while q:
        l=q.pop(0)
        bfs(l[0],l[1],count)
        
    q=temp[:]
    if len(q)==0:
        print(-1)
        exit()