Harryxun/stf_run huggingface dataset:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    K = int(input())

    nstr = str(N)

    nl = len(str(N))

    dp = [[[0 for _ in range(nl + 1)] for _ in range(2)] for _ in range(nl + 1)]
    dp[0][0][0] = 1

    for i in range(nl):
        max_digit = int(nstr[i])
        for smaller in range(2):
            for j in range(nl):
                range_digit = 9
                # range_digit = 9 if smaller else max_digit
                if not smaller:
                    range_digit = max_digit
                for x in range(range_digit + 1):
                    if x != 0:
                        if smaller == 1:
                            dp[i + 1][smaller][j + 1] += dp[i][smaller][j]
                        else:
                            if x < max_digit:
                                dp[i + 1][1][j + 1] += dp[i][smaller][j]
                            else:
                                dp[i + 1][0][j + 1] += dp[i][smaller][j]
                    else:
                        if smaller == 1:
                            dp[i + 1][smaller][j] += dp[i][smaller][j]
                        else:
                            if x < max_digit:
                                dp[i + 1][1][j] += dp[i][smaller][j]
                            else:
                                dp[i + 1][0][j] += dp[i][smaller][j]

    ans = 0
    print(dp[nl][1][K])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from functools import lru_cache

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 8)


@lru_cache(maxsize=None)
def solve(n, k):
    if n < 10:
        if k == 1:
            return n
        elif k == 0:
            return 1
        else:
            return 0

    q, r = divmod(n, 10)

    return solve(q, k) + solve(q, k - 1) * r + solve(q - 1, k - 1) * (9 - r)


def main():
    N = int(input())
    K = int(input())

    print(solve(N, K))


if __name__ == '__main__':
    main()
n,t = map(int,input().split())
d = []

for i in range(n):
    c,s = map(int,input().split())
    if s <= t:
        d.append(c)
if d == 0:
    print("TLE")
else:
    print(min(d))

### FIXED CODE ###

n,t = map(int,input().split())
d = []

for i in range(n):
    c,s = map(int,input().split())
    if s <= t:
        d.append(c)
if d== []:
    print("TLE")
else:
    print(min(d))
#! -*- coding:utf-8 -*-

def search(values,hp,vp,item):
	if not (0<=hp<len(values)): return
	if not (0<=vp<len(values[hp])): return
	if item!=values[hp][vp]: return
	values[hp][vp]=True
	search(values,hp-1,vp,item)
	search(values,hp+1,vp,item)
	search(values,hp,vp-1,item)
	search(values,hp,vp+1,item)

def solve(values):
	count=0
	for i in range(len(values)):
		for j in range(len(values[i])):
			if values[i][j] in ['@','#','*']:
				search(values,i,j,values[i][j])
				count+=1
	return count

def main():
	line,values=raw_input(),list()
	while line!='0 0':
		H,W = list(map(int,line.strip().split(' ')))
		value = list()
		for _ in range(H):
			value.append([x for x in raw_input().strip()])
		values.append(value)
		line = raw_input()
	for value in values:
		print solve(value)

if __name__=='__main__':
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**6)

def search(field,hp,vp,item):
	if not (0<=hp<len(field)): return
	if not (0<=vp<len(field[hp])): return
	if item!=field[hp][vp]: return
	field[hp][vp]=True
	for dh,dv in [[0,1],[0,-1],[1,0],[-1,0]]:
		search(field,hp+dh,vp+dv,item)
#	search(field,hp-1,vp,item)
#	search(field,hp+1,vp,item)
#	search(field,hp,vp-1,item)
#	search(field,hp,vp+1,item)

def solve(field):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(field)):
		for j in range(len(field[i])):
			if field[i][j] in valid_items:
				search(field,i,j,field[i][j])
				count+=1
	return count

def main():
	line = input().strip()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		field = list()
		for _ in range(H):
			field.append(list(input().strip()))
		print(solve(field))
		line = input().strip()

if __name__=='__main__':
	main()
min=10
sum=0
for i in range(5):
  y=int(input())
  x=10-y%10
  min=min(min, x)
  if x==min:
    sum+=y
  else:
    sum+=y+x
print(sum)

### FIXED CODE ###

X=[int(input()) for i in range(5)]
Y=[]
for x in X:
  Y.append(-(-x//10)*10-x)
print(sum(X)+sum(Y)-(max(Y)))
N,X = map(int,input().split())
L = list(map(int,input().split()))
D,i,cnt = 0,0,0
while(D <= X and cnt <= N):
  D = D + L[i]
  cnt +=1
  i += 1
print(cnt)

### FIXED CODE ###

N,X = map(int,input().split())
L = list(map(int,input().split()))
L.append(0)
D,i,cnt = 0,0,0
while(D <= X and cnt <= N):
  D = D + L[i]
  cnt +=1
  i += 1
print(cnt)
s = input()
imin = 753
for i in range(len(s)-2):
  if(abs(int(s[i] + s[i+1] + s[i+2]) - 753) < imin:
     imin = abs(int(s[i] + s[i+1] + s[i+2])-753)
print(imin)

### FIXED CODE ###

s = input()
imin = 753
for i in range(len(s)-2):
  if(abs(int(s[i] + s[i+1] + s[i+2]) - 753) )< imin:
     imin = abs(int(s[i] + s[i+1] + s[i+2])-753)
print(imin)
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))
dp = [[0 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
  for j in range(S+1):
    dp[i+1][j] += 2*dp[i][j]
    dp[i+1][j] %= mod
    if j + A[i] <=S:
      dp[i+1][j+A[i]] += dp[i][j]
      dp[i+1][j+A[i]] %= mod
print(dp[N][S]%mod)

### FIXED CODE ###

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

A, B = map(int, readline().split())
print(A*B)
N = int(input())
S=[]
for n in range(N):
    S.append(input())
Slist = []
for s in S:
    lists = list(s)
    listss = sorted(lists)
    Slist.append(listss)
def isAna2(Sl,sl):
    boolcount = True
    for i,Sli in enumerate(Sl):
        if Sli != sl[i]:
            boolcount = False
            break
    return boolcount
count = 0
for i,Sl in enumerate(Slist):
    for sl in Slist[i+1:]:
        if isAna2(Sl,sl) == True:
            count+=1
print(count)

### FIXED CODE ###

A,B = map(int,input().split())
a = max(A+B, A-B, A*B)
print(a)
N,M = map(int,input().split())
import numpy as np
A = sorted(np.array(list(map(int,input().split()))),reverse=True)
ans = 0
while M>0:
  a = A.pop(0)
  ans += a*2
  M-=1
  print(a)
  if (M>0)and(a>=A[0]*2):
    for i in A:
      ans+=(i+a)*2
      M-=2
      if M==0:
        break
      elif M<0:
        ans-=(i+a)
        break
        
  elif (M>0)and(a<A[0]*2):
    b=A[0]*2-a
    for i in A:
      if i>=b:
        ans+=(i+a)*2
        M-=2
        if M==0:
          break
        elif M<0:
          ans-=(i+a)
          break
      else:
        break
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
bi = [0]*(A[0]+1)
for a in A:
  bi[a]+=1
  
cum = [0]*(A[0]+1)
for i in range(1,A[0]+1):
  cum[i]=cum[i-1]+bi[i]

cum_max=cum[-1]
left = 0
right = A[0]*2+1
while right-1!=left:
  x = (right+left)//2
  num = 0
  for a in A:
    b = max(x-a,1)
    if b<=A[0]:
      num += cum_max-cum[b-1]
    
  if num>=M:
    left=x
  else:
    right=x

ans = 0
cum_A = [0]*(N+1)
for i in range(1,N+1):
  cum_A[i]=cum_A[i-1]+A[i-1]
for a in A:
  b = max(right-a,1)
  if b>A[0]:
    break
  c = cum_max-cum[b-1]
  M-=c
  ans+=(a*c)+cum_A[c]
  

ans+=M*left
print(ans)
count = 0
a = input()
b = input()

for i in len(a):
    if a[i]!=b[i]:
        count += 1

print(count)

### FIXED CODE ###

count = 0
a = input()
b = input()

for i in range(len(a)):
    if a[i]!=b[i]:
        count += 1

print(count)
import math
A, B = list(map(decimal, input().split()))
B = B*100
print(math.floor(A*B/100))

### FIXED CODE ###

import math
from decimal import *
A, B = list(map(Decimal, input().split()))
print(math.floor(A*B))
from collections import deque

n,m = map(int,input().split())
map_li = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    map_li[a].append(b)
    map_li[b].append(a)

ans_li = [-1]*n
queue=deque()
queue.append(0)

while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if ans_li[g]==-1:
            ans_li[g]=x
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)

### FIXED CODE ###

n,m = map(int,input().split())
map_li = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    map_li[a].append(b)
    map_li[b].append(a)

ans_li = [-1]*n
queue=[0]
visited = [False]*n

while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)
h,w,k = map(int, input().split())

r_n = [0]*h
c_n = [0]*w
bomb_table = set()
for i in range(m):
	hi, wi = map(int, input().split())
	hi-=1
	wi-=1
	r_n[hi] += 1
	c_n[wi] += 1
	bomb_table.add((hi, wi))

max_x = max(c_n)
max_y = max(r_n)
ans = max_x + max_y

for i in range(h):
	if r_n[i] != max_y:
		continue
	for j in range(w):
		if c_n[j] != max_x:
			continue
		if (i,j) not in bomb_table:
			print(ans)
			exit()
			
print(ans - 1)

### FIXED CODE ###

h, w, k = map(int, input().split())

r_n = [0] * h
c_n = [0] * w
bomb_table = set()
for i in range(k):
    hi, wi = map(int, input().split())
    hi -= 1
    wi -= 1
    r_n[hi] += 1
    c_n[wi] += 1
    bomb_table.add((hi, wi))

max_x = max(c_n)
max_y = max(r_n)
ans = max_x + max_y

max_x_table = set()
max_y_table = set()

for i in range(h):
    if r_n[i] == max_y:
        max_y_table.add(i)

for i in range(w):
    if c_n[i] == max_x:
        max_x_table.add(i)

for i in max_y_table:
    for j in max_x_table:
        if (i, j) not in bomb_table:
            print(ans)
            exit(0)
print(ans - 1)
import sys
input = sys.stdin.readline
import numpy as np

def standard_form(A):
    for k in range(60,-1,-1):
        bit = 1<<k
        exists = A&bit==bit
        used = A>2*bit
        i = np.where(exists & ~used)[0]
        if len(i) == 0:
            continue
        i = i[0]
        x = A[i]
        A[exists] ^= x
        A[i] = x
    return A



t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    A = []
    B = []

    task = set([0])

    now = s[n-1]
    if now == "1":
        print(1)
        continue


    q = []
    win = "0"
    for i in range(n-1, -1, -1):
        if now == "0":
            if s[i] == "0":
                q.append(a[i])
            else:
                q = standard_form(np.array(q, np.int64))
                task = task | set(q)
                task = standard_form(np.array(list(task), np.int64))
                task = set(task)
                q = [a[i]]
                now = "1"
        else:
            if s[i] == "1":
                q.append(a[i])
            else:
                q = standard_form(np.array(q, np.int64))
                if task != task | set(q):
                    win = "1"
                    break

                q = [a[i]]
                now = "0"

    if now == "1":
        q = standard_form(np.array(q, np.int64))
        if task != task | set(q):
            win = "1"

    print(win)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def standard_form(A):
    C = A[:]
    L = 60
    E = []
    ids = []
    for i in range(L):
        e = j0 = None
        mask = (1 << i)-1
        for j, a in enumerate(C):
            if (a >> i) & 1 and (a & mask) == 0:
                e = a
                j0 = j
                break
        else:
            continue
        ids.append(j0)
        for j, a in enumerate(C):
            if j0 == j:
                continue
            if (a >> i) & 1:
                C[j] ^= e
    return [C[e] for e in ids]


t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = input()
    A = []
    B = []

    task = set([0])

    now = s[n-1]
    if now == "1":
        print(1)
        continue


    q = []
    win = "0"
    for i in range(n-1, -1, -1):
        if now == "0":
            if s[i] == "0":
                q.append(a[i])
            else:
                q = standard_form(q)
                task = task | set(q)
                task = set(standard_form(list(task)))
                q = [a[i]]
                now = "1"
        else:
            if s[i] == "1":
                q.append(a[i])
            else:
                q = standard_form(q)
                q = set(q) | task
                q = set(standard_form(list(q)))
                if task != task | q:
                    win = "1"
                    break

                q = [a[i]]
                now = "0"

    if now == "1":
        q = standard_form(list(q))
        q = set(q) | task
        q = standard_form(list(q))
        q = set(q)
        if task != task | q:
            win = "1"

    print(win)
h, w = input().split()
n = int(h) * int(w)
a = n//2
if h==1 or w==1:
  print(1)
  
elif n%2==1:
  print(a+1)
  
else:
  print(a)


### FIXED CODE ###

l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
k -= 1
print(l[k])
import math
import numpy as np
import matplotlib.pyplot as plt

#def main(S, b):
if __name__ == '__main__':
    a = input()
    b = a.upper()

    if (a == b):
        print('A')
    else:
        print("a")


### FIXED CODE ###

if __name__ == '__main__':
    a = input()
    b = a.upper()

    if (a == b):
        print('A')
    else:
        print("a")
# -*- coding: utf-8 -*-
s = input()
K = int(input())


def substring(s, K):
    substrings = []
    length = len(s)
    for i in range(length):
        for j in range(K+1):
            if i + j >= length:
                break
            substrings.append(s[i:i+j])
    return substrings[K]


print(substring(s, K))


### FIXED CODE ###

# -*- coding: utf-8 -*-
s = input()
K = int(input())


def substring(s, K):
    substrings = []
    length = len(s)
    for i in range(length):
        for j in range(1, K+1):
            if i + j > length:
                break
            substrings.append(s[i:i + j])
    unique_substrings = list(set(substrings))
    unique_substrings.sort()
    return unique_substrings[K - 1]


print(substring(s, K))
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n = int(input())
list_ABC = [ list(map(int,input().split(" "))) for i in range(n-1)]
q, k = map(int, input().split())
list_XY = [ list(map(int,input().split(" "))) for i in range(q)]

ma = np.zeros((n,n), dtype=np.int16)
for a, b, c in list_ABC:
    ma[a-1, b-1] = c
    ma[b-1, a-1] = c

a = csr_matrix(ma)
b = dijkstra(a, directed=False).astype(int)

for x, y in list_XY:
    print(b[x-1, k-1]+b[k-1, y-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])
S1=list(S)
print(S1)
if S1[2]==S1[3] and S1[4]==S1[5]:
    print("Yes")
else : 
    print("No")



### FIXED CODE ###

S=input()
if S[2]==S[3] and S[4]==S[5]:
    print("Yes")
else : 
    print("No")
n = int(input())
seen = set()
ans = 0
res = 7%n
seen.add(res)
ans += 1
while res != 0:
	new = (res*10 + 7)%n
    if new not in seen:
		seen.add(new)
        res = new
        ans += 1
	else:
    	print(-1):
        exit()
print(ans)

### FIXED CODE ###

k = int(input())
ans = 1
seen = set()
mod = 7%k
while mod != 0 and mod not in seen:
    seen.add(mod)
    mod = (10*mod + 7)%k
    ans += 1

if mod == 0:
    print(ans)
else:
    print(-1)
N = int(input())
ans = []
for i in range(2,35):
    for j in range(2,11):
        if i**j <= N:
            ans.append(i**j)
print(max(ans))


### FIXED CODE ###

N = int(input())
ans = []
for i in range(1,35):
    for j in range(2,11):
        if i**j <= N:
            ans.append(i**j)
print(max(ans))
s=input()
S=list(s)
cc=0
for i in range(2,len(S)-1):
  if S[i]=='C':
    cc=cc+1
    S.remove(S[i])
S.remove(S[0])
count=[]
if s[0]=='A':
  count.append(1)
if cc==1:
  count.append(2)
if ''.join(S).islower():
  count.append(3)

if count==[1,2,3]:
  print('AC')
else:
  print('WA')

### FIXED CODE ###

s=input()
S=list(s)
cc=0
for i in range(2,len(S)-1):
  if S[i]=='C':
    cc=cc+1
if cc>=1:
  S.remove('C')
S.remove(S[0])
count=[]
if s[0]=='A':
  count.append(1)
if cc==1:
  count.append(2)
if ''.join(S).islower():
  count.append(3)

if count==[1,2,3]:
  print('AC')
else:
  print('WA')
s = input()
for _ in range(len(s)):
  print(x,end='')

### FIXED CODE ###

s = input()
for _ in range(len(s)):
  print('x',end='')
import math
import fractions
A,B = map(int,input().split())

maxn=fractions.gcd(A,B)
list=[]
def isPrime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    m = math.floor(math.sqrt(n)) + 1
    for p in range(3, m, 2):
        if n % p == 0:
            return False
        return True
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

yaku=make_divisors(maxn)
for i in range(len(yaku)):
    if isPrime(yaku[i]):
        list.append(yaku[i])

print(len(list))


### FIXED CODE ###

N=int(input())
if N%2==0:
  print((N/2)/N)
else:
  print(((N+1)/2)/N)
a = input()
b = input()
if a = 'chokudai' and b = 'chokudaiz' or a = 'a' and b = 'aa':
    print("Yes")
elif a = 'snuke' and b = 'snukee':
    print("No")

### FIXED CODE ###

s = input()
t = input()
check = t[:-1]
a = len(s)
b = len(t) - 1
if a == b:
    if s == check:
        print("Yes")
    else:
        print("No")
else:
    print("No")
import math
a,b,x=map(int,input().split())
if (a*a*b)>=2*x:
  h=x/(b*(a/2))
  print(90-math.degrees(math.atan(h/b)))
else:
  h=(((x/a)*2)/a)-b
  b-=h
  print(90-math.degrees(math.atan(a/b)))

### FIXED CODE ###

import math
a,b,x=map(int,input().split())
if (a*a*b)>=2*x:
  h=x/(b*(a/2))
  print(90-math.degrees(math.atan(h/b)))
else:
  h=(((x/a)*2)/a)-b
  b-=h
  if b!=0:
    print(90-math.degrees(math.atan(a/b)))
  else:
    print(0)
def get_match_list(num_list, num_num):
    match_num_list = set()
    match_dic = [2,5,5,4,5,6,3,7,6]
    for num in num_list:
        match_num_list.add(match_dic[num-1])
    match_num_list = list(match_num_list)
    match_num_list.sort()
    return match_num_list

def get_dp(use_match_list, match_nun):
    dp = [-1 for i in range(match_nun + 1)]
    dp[0] = 0
    for i in range(2, match_nun + 1):
        for macth_bar in use_match_list:
            if dp[i-macth_bar] >= 0:
                dp[i] = dp[i-macth_bar] + 1
                break
    return dp

def print_ans(dp, match_nun, num_list):
    match_dic = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    max_ketasuu = dp[match_nun]
    ans = ''
    while match_nun > 0:
        for num in num_list:
            use_match_num = match_dic[num - 1]
            if dp[match_nun - use_match_num] == max_ketasuu - 1:
                ans += str(num)
                match_nun -= use_match_num
                max_ketasuu -= 1
                break
    print(ans)



def main():
    match_nun, num_num = map(int, input().split())
    num_list = list(map(int, input().split()))
    num_list.sort(reverse=True)
    use_match_list = get_match_list(num_list, num_num)
    dp = get_dp(use_match_list, match_nun)
    print_ans(dp, match_nun, num_list)


if __name__ == '__main__':
    main()

### FIXED CODE ###


def get_match_list(num_list, num_num):
    match_num_list = set()
    match_dic = [2,5,5,4,5,6,3,7,6]
    for num in num_list:
        match_num_list.add(match_dic[num-1])
    match_num_list = list(match_num_list)
    match_num_list.sort()
    return match_num_list

def get_dp(use_match_list, match_nun):
    dp = [-1 for i in range(match_nun + 1)]
    dp[0] = 0
    for i in range(2, match_nun + 1):
        for macth_bar in use_match_list:
            if dp[i-macth_bar] >= 0:
                dp[i] = dp[i-macth_bar] + 1
                break
    return dp

def print_ans(dp, match_nun, num_list):
    match_dic = [2, 5, 5, 4, 5, 6, 3, 7, 6]
    max_ketasuu = dp[match_nun]
    ans = ''
    while match_nun > 0:
        for num in num_list:
            use_match_num = match_dic[num - 1]
            if match_nun - use_match_num < 0:
                continue
            if dp[match_nun - use_match_num] == max_ketasuu - 1:
                ans += str(num)
                match_nun -= use_match_num
                max_ketasuu -= 1
                break
    print(ans)



def main():
    match_nun, num_num = map(int, input().split())
    num_list = list(map(int, input().split()))
    num_list.sort(reverse=True)
    use_match_list = get_match_list(num_list, num_num)
    dp = get_dp(use_match_list, match_nun)
    print_ans(dp, match_nun, num_list)


if __name__ == '__main__':
    main()
n,k = map(int,input().split())
s = input()
lr_cnt = 0
rl_cnt = 0
mnt = 0
for i in range(len(s)-1):
    if s[i] == 'L' and s[i+1] == 'R':
        lr_cnt += 1
        
    if s[i] == 'R' and s[i+1] == 'L':
        rl_cnt += 1
mnt  = rl_cnt + lr_cnt+1
mnt = np.max([1,mnt-2*k])
if mnt == 1:
    print(n-1)
else:
    print(n-rl_cnt-lr_cnt+2*k-1)

### FIXED CODE ###

import numpy as np
n,k = map(int,input().split())
s = input()
lr_cnt = 0
rl_cnt = 0
mnt = 0
for i in range(len(s)-1):
    if s[i] == 'L' and s[i+1] == 'R':
        lr_cnt += 1
        
    if s[i] == 'R' and s[i+1] == 'L':
        rl_cnt += 1
mnt  = rl_cnt + lr_cnt+1
mnt = np.max([1,mnt-2*k])
if mnt == 1:
    print(n-1)
else:
    print(n-rl_cnt-lr_cnt+2*k-1)
import math

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

if n>=b:
	n1 = n//b*b-1
	n2 = n//b*b-2
	ans = max(math.floor(a*n/b)-a*math.floor(n/b), max(math.floor(a*n1/b)-a*math.floor(n1/b)), math.floor(a*n2/b)-a*math.floor(n2/b))
else:
	ans = math.floor(a*n/b)-a*math.floor(n/b)

print(ans)

### FIXED CODE ###

import math

a, b, n = map(int, input().split())
x = min(n, b-1)
print(math.floor(a*x/b)-a*math.floor(x/b))
import fractions

N=int(input())
t,a=1,1
for i in range(N):
    T,A=map(int,input().split())
    # n=max(-(-a//A),-(-t//T))
    n=max(fractions.ceil(a/A),fractions.ceil(t/T))
    t,a=n*T,n*A

print(t+a)


### FIXED CODE ###

import fractions

N=int(input())
t,a=1,1
for i in range(N):
    T,A=map(int,input().split())
    n=max(-(-a//A),-(-t//T))
    # n=max(fractions.ceil(a/A),fractions.ceil(t/T))
    t,a=n*T,n*A

print(t+a)
N, A, B = map(int,input().split())

q, x = divmod(N, A+B)
#q = N//(A+B)
#x = N % (A+B)
ans = q*A+int(min(x,A))
#print(type(ans))
print(ans

### FIXED CODE ###

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

q, x = divmod(N, A+B)
#q = N//(A+B)
#x = N % (A+B)
ans = q*A+int(min(x,A))
#print(type(ans))
print(ans)
n = int(input())
a = map(int, input().split())
c = 0
for i in range(n):
  if a[a[i]] == i:
    c++
print(c)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
c = 0
for i in range(n):
  if a[a[i] - 1] - 1 == i:
    c += 1
print(c // 2)
n=int(input())
A=[int(i) for i in input().split()]
prod=1
for i in range(0,N):
  prod=prod*A[i]
  if(prod>1000000000000000000):
    prod=-1
    break
print(prod)

### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
A.sort()
prod=1
for i in range(0,n):
  prod=prod*A[i]
  #print(prod)
  if(prod==0):
      break
  if(prod>1000000000000000000):
    prod=-1
    break
print(prod)
n=int(input())
a=[]
for i in range(1,10):
    for j in range(1,i+1):
        a.append(i*j)
if n in a:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b=map(int,input().split())
if (1 <= a <= 9) and (1 <= b <= 9):
    print(a*b)
else:
    print(-1)