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

from collections import defaultdict

n, k = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1])
t = defaultdict(int)
x = list(range(n - 1, n - k - 1, -1))
z = [0]
for i in range(n - k, n):
    t[sushi[i][0]] += 1
    z[0] += sushi[i][1]

y = []
yd = list(t.keys())
for i in range(n - k - 1, -1, -1):
    if sushi[i][0] not in yd:
        y.append(i)
        yd.append(sushi[i][0])
y = y[::-1]
k = 1

for k in range(1, len(y) + 1):
    for i in range(len(x) - 1, -1, -1):
        xi = x[i]
        if t[sushi[xi][0]] > 1:
            t[sushi[xi][0]] -= 1
            z.append(z[-1] - sushi[xi][1] + sushi[y[-k]][1])
            x.pop(i)
            break

p = len(t.keys())
ans = 0
for i in range(len(z)):
    ans = max(ans, z[i] + (p + i) ** 2)
print(ans)


### FIXED CODE ###

import heapq

n, k = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1])
t = {}
x = []
z = 0
for i in range(n - 1, n - k - 1, -1):
    ti, di = sushi[i]
    if ti in t.keys():
        heapq.heappush(x, di)
        t[ti] += 1
    else:
        t[ti] = 1
    z += di

p = len(t.keys())
ans = z + p ** 2
for i in range(n - k - 1, -1, -1):
    if len(x) == 0:
        break
    ti, di = sushi[i]
    if ti not in t.keys():
        t[ti] = 1
        z += di - heapq.heappop(x)
        p += 1
        ans = max(ans, z + p ** 2)

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

#!/usr/bin/env python3
 
import sys
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()


def main():
    input = sys.stdin.readline      # 改行文字が残ることに注意
    def ii():  return int(input())
            

    def bfs_tree_traverse(root):
        ' root から BFS し条件を満たすように彩色していく。各辺の色情報を color に記載。最後に使用した色の数を返す。'
        paths = deque([root])
        max_branch = 0
        while len(paths) != 0:
            edge_color = 0
            current = paths.popleft()
            if current == root:
                parent = -1
                parent_color = -1
            else:
                parent = adj[current][0]
                parent_color = color[parent][current]
            for v in adj[current]:
                if v != parent:
                    paths.append(v)
                    edge_color += 1
                    if edge_color == parent_color:
                        edge_color += 1
                    color[current][v] = edge_color
                max_branch = max(max_branch, edge_color)
        return max_branch
        
 
    n = ii()
    # 各辺の両端の頂点 index を保存したペア (tuple) の list
    L = [tuple(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(n-1)]
    # 隣接リスト
    adj = [[] for _ in range(n)]
    for pair in L:
        a, b = pair
        adj[a].append(b)
        adj[b].append(a)
    # 色情報 (int) が記載される隣接行列
    color = [[None] * n for _ in range(n)]
    
    print(bfs_tree_traverse(0))
    for pair in L:
        a, b = pair
        print(color[a][b])
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3
 
import sys
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()


def main():
    input = sys.stdin.readline      # 改行文字が残ることに注意
    def ii():  return int(input())
            

    def bfs_tree_traverse(root):
        ' root から BFS し条件を満たすように彩色していく。各辺の色情報を color に記載。最後に使用した色の数を返す。'
        paths = deque([root])
        max_branch = 0
        while len(paths) != 0:
            edge_color = 0
            current = paths.popleft()
            parent_edge_color = color[current]
            for v in adj[current]:
                paths.append(v)
                edge_color += 1
                if edge_color == parent_edge_color:
                    edge_color += 1
                color[v] = edge_color
                max_branch = max(max_branch, edge_color)
        return max_branch
        
 
    n = ii()
    # 各辺の両端の頂点 index を保存したペア (tuple) の list
    L = [tuple(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(n-1)]
    # 隣接リスト 親->子のみリンクをはれば十分
    adj = [[] for _ in range(n)]
    for pair in L:
        a, b = pair
        adj[a].append(b)
    # 各辺の子供の index と色情報 (int) の対応記載される隣接行列 
    color = [0] * n
    
    print(bfs_tree_traverse(0))
    for pair in L:
        _, b = pair
        print(color[b])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math

n, d, a = map(int,input().split())
xh = []
for i in range(n):
    x,h = map(int,input().split())
    xh.append([x,h])

num = 0
xh.sort(key=lambda xh:xh[0])
l = len(xh)
dam = [0]*n
rang = [0]*n
for i in range(n):
    rang[i] = xh[i][0]-2*d

for i in range(n):
    res = xh[i][1]-dam[i]
    if res > 0:
        nat = math.ceil(res/a)
        pos = xh[i][0]
        num += nat
        for j in range(i+1,n):
            if rang[j] <= pos:
                dam[j] += a*nat
            else:
                break
print(num)


### FIXED CODE ###

import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
left = [i for i in range(n)]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh.sort(key=lambda xh:xh[0])

for i in range(n):
    for j in range(left[i-1],i):
        if xh[j][0]+d >= xh[i][0]-d:
            left[i] = j
            break

dam = [0]*n

def dsum(k):
    if k == 0:
        return 0
    elif left[k] == 0:
        return dam[k-1]
    else:
        return dam[k-1]-dam[left[k]-1]

for i in range(n):
    res = xh[i][1]-dsum(i)
    nat = max([math.ceil(res/a),0])
    dam[i] = dam[i-1]+a*nat
    if res > 0:
        num += nat

print(num)
### BUGGY CODE ###

n,m = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([-a,b])
ab.sort()
ab.reverse()
#print(ab)
here = 0
ans = 0
pool = [0 for _ in range(10**4+1)]
#maxi = 0
cnt = 0
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      add = ab[here][1]
      pool[add] += 1
      '''
      if add > maxi:
        maxi = add
      '''
      here += 1
      cnt += 1
    else:
      break
  if cnt != 0:
    cnt -= 1
    for j in range(10**4):
      if pool[10**4-j] != 0:
        ans += 10**4-j
        #print(10**4-j,i)
        pool[10**4-j] -= 1
        break
    '''
    ans += maxi
    pool[maxi] -= 1
    if pool[maxi] == 0:
      if cnt == 0:
        maxi = 0
      else:
        while True:
          maxi -= 1
          if pool[maxi] != 0:
            break
    '''
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([-a,b])
ab.sort()
ab.reverse()
#print(ab)
here = 0
ans = 0
pool = []
import heapq
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      heapq.heappush(pool,-ab[here][1])
      here += 1
    else:
      break
  try:
    #print(pool)
    ans -= heapq.heappop(pool)
    #print(pool)
  except:
    pass
print(ans)
### BUGGY CODE ###

n=input()
keta=len(n)
n=int(n)
satsu=0

for i in range(keta+1):
	tmp = n % 10
	n = n//10
	if tmp == 5 and n % 10 >= 5:
		satsu += 10 - tmp
		n += 1
	
	elif 0 <= tmp <= 5:
		satsu += tmp
	else:
		satsu += 10 - tmp
		n += 1

print(satsu)



### FIXED CODE ###

n=list(map(int,input()))
keta=len(n)
satsu=0

for i in range(keta):
    tmp = n.pop()
    if i == keta-1:
        n.append(0)
    
    if tmp == 10:
        tmp=0
        n[-1]=n[-1]+1
    if tmp > 5 or (tmp==5 and n[-1] >= 5):
        satsu += 10 - tmp
        n[-1] = n[-1] + 1
    else:
        satsu += tmp

print(satsu+n[0])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in range(n):
    ans=a[i]*ans

if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

a.sort()
if a[0]==0:
    print(0)
else:
    a.sort(reverse=True)
    # print(a)

    ans=1
    for i in range(n):
        ans=a[i]*ans
        if ans>10**18:
            break

    if ans>10**18:
        print(-1)
    else:
        print(ans)
### BUGGY CODE ###

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

n, m = input().split()
x = input().split()
y = input().split()
width = [abs(int(x[i])-int(x[j])) for i in range(len(x)-1) for j in range(i+1, len(x))]
height = [abs(int(y[i])-int(y[j])) for i in range(len(y)-1) for j in range(i+1, len(y))]

sum = 0
for w in width:
    for h in height:
        sum = sum + w * h
print(sum % (10 ** 9 + 7))


### FIXED CODE ###

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

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

def sum_length(x, n):
    all_sum = 0
    prev_sum = 0
    for i in range(1, n):
        cur_sum = prev_sum + (x[i] - x[i-1]) * i
        all_sum = all_sum + cur_sum
        prev_sum = cur_sum
    return all_sum

sumx = sum_length(x, n)
sumy = sum_length(y, m)
print(sumx * sumy % 1000000007)
### BUGGY CODE ###

import scipy.linalg as linalg
import numpy as np
N = int(input())
A = list(map(int,input().split()))
#
b = np.array([a*2 for a in A])
A = []
for i in range(N):
    a = [0]*N
    if i==N-1:
        a[0]=1
        a[N-1]=1
    else:
        a[i]=1
        a[i+1]=1
    A.append(a)
A = np.array(A)
LU = linalg.lu_factor(A)
x = linalg.lu_solve(LU,b)
x = [int(a) for a in x]
print(*x)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
# solve
x = 0
for i in range(N):
    if i%2==0:
        x+=A[i]
    else:
        x-=A[i]
ans = [x]
for i in range(N-1):
    x = ans[i]
    ans.append(2*A[i]-x)
print(*ans)
### BUGGY CODE ###

n = int(input())
v = [input() for _ in range(n)]
V = sorted(v)

cnt = 0

for i in range(n):
    V[i] = sorted(V[i])

for i in range(n):
    for j in range(n):
        if V[i] == V[j] and i!=j:
            cnt += 1
            
print(int(cnt/2))

### FIXED CODE ###

n = int(input())
s = ([''.join(sorted(input())) for _ in range(n)])
S = sorted(s)
D = {}#辞書
ans = 0
for i in S:
    #print('i:'+str(i))
    if i in D:
        #print('ii:'+str(i))
        D[i] += 1
        ans += D[i]
    else:
        D[i] = 0
#print(D)
print(ans)
### BUGGY CODE ###

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

A = []
B = []

for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

dp = [1e9]*(H+1)
dp[0] = 0
for i in range(N):
    for j in range(H+1):
        if dp[min(j+A[i],H)] > dp[j] + B[i]:
            dp[min(j+A[i],H)] = dp[j]+B[i]
    
print(dp[H])

### FIXED CODE ###

H,N = map(int,input().split())
AB = [list(map(int, input().split())) for i in range(N)]

M = max(a for a,b in AB)

dp = [0]*(H+M)

for i in range(1,H+M):
    dp[i] = min(dp[i-a]+b for a,b in AB)
    
print(min(dp[H:]))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N):
    copy = A[:]
    copy.pop(i)
    print(max(copy))


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

ans = []
front_max_list, back_max_list = [0], [0]

for i in range(N):
    front_max_list.append(max(front_max_list[i], A[i]))
    back_max_list.append(max(back_max_list[i], A[N - i - 1]))

for i in range(N):
    print(max(front_max_list[i], back_max_list[N - i - 1]))
### BUGGY CODE ###

H,W = map(int,input().split())
INF = 10**10
trout = [[INF for i in range(W)]for i in range(H)]
q = []
for h in range(H):
  row = list(input())
  for w in range(W):
    if row[w]=='#':
      q.append([h-1,w])
      q.append([h+1,w])
      q.append([h,w-1])
      q.append([h,w+1])
      trout[h][w] = 0
while len(q)!=0:
  h,w = q[0][0],q[0][1]
  del q[0]
  if h<0 or H<=h or w<0 or W<=w:
    continue
  if trout[h][w]!=INF:
    continue
  if trout[h][w]==INF:
    s = []
    if 0<=h-1:
      s.append(trout[h-1][w])
    if h+1<H:
      s.append(trout[h+1][w])
    if 0<=w-1:
      s.append(trout[h][w-1])
    if w+1<W:
      s.append(trout[h][w+1])
    trout[h][w] = min(s)+1
  q.append([h-1,w])
  q.append([h+1,w])
  q.append([h,w-1])
  q.append([h,w+1])
res = 0
for h in range(H):
  res = max([res]+trout[h])
print(res)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
S = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            S[h][w] = H*W
for h in range(H):
    a = 0
    for w in range(W):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for w in range(W)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
for w in range(W):
    a = 0
    for h in range(H):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for h in range(H)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
ans = H*W
for h in range(H):
    for w in range(W):
        ans = min(ans,S[h][w])
print(H*W-ans)
### BUGGY CODE ###

N = int(input())
t, a = 1, 1

for _ in range(N):
  _t, _a = map(int, input().strip().split())
  if _t > _a:
    i = t // _t
  else:
    i = a // _a
  while True:
    if _t*i>=t and _a*i>=a:
      break
    else:
      i += 1
  t = _t*i
  a = _a*i
print(t+a)
    

### FIXED CODE ###

N = int(input())
t, a = 1, 1

for _ in range(N):
  _t, _a = map(int, input().split())
  n = max(-(-t // _t), -(-a // _a))
  t, a = n*_t, n*_a
print(t + a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, b = map(int, input().split())
    c = set(map(int, input().split()))
    keys.append((a, c))

ans = 10**7

def solve(i, cost, key_set):
    global ans
    if i==m:
        return
    tmp = key_set.copy()
    tmp |= keys[i][1]
    if len(tmp)==n:
        ans = min(ans, cost+keys[i][0])
    else:
        solve(i+1, cost+keys[i][0], tmp)
    solve(i+1, cost, key_set)

solve(0, 0, set())
print(ans if ans<10**7 else -1)

### FIXED CODE ###

INF = 10**9
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = 0
    for i in input().split():
        c += 2**(int(i)-1)
    keys.append((a, c))

dp = [INF]*(2**n)
dp[0] = 0
for a, c in keys:
    tmp = [INF]*(2**n)
    for j, d in enumerate(dp):
        if d == INF:
            continue
        if d < tmp[j]:
            tmp[j] = d
        if d+a < tmp[j|c]:
            tmp[j|c] = d+a
    dp = tmp

print(dp[-1] if dp[-1]<INF else -1)
### BUGGY CODE ###

from sys import stdin

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

for i in range(q):
    kotoba = s[li[i][0]-1:li[i][1]]
    kai = kotoba.count("AC")
    print(kai)

### FIXED CODE ###

from sys import stdin
import bisect

n,q = [int(x) for x in stdin.readline().rstrip().split()]
s = stdin.readline().rstrip()
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
lin = []
point = 0
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        lin.append(i+1)
for j in range(q):
    hi = bisect.bisect(lin,li[j][1]-1)
    lo = bisect.bisect(lin,li[j][0]-1)
    print(hi-lo)
### BUGGY CODE ###

from collections import defaultdict, Counter
def factors(N): #約数を全て求める。ただし、順不同
    from collections import deque
    ret = deque()
    middle = int( N**(1/2))
    for i in range(1, middle):
        if N%i == 0:
            ret.append(i)
            ret.append(N//i)
            
    if N%middle == 0:
        ret.append(middle)
        if middle != N//middle:
            ret.append(N//middle)
    return ret

def main():
    N = int( input())
    A = list( map( int, input().split()))
    CA = Counter(A)
    d = defaultdict( lambda : False)
    for a in A:
        d[a] = True
    ans = 0
    for a in A:
        if CA[a] > 1:
            continue
        for p in factors(a):
            if p == a:
                continue
            if d[p]:
                break
        else:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter, defaultdict
def main():
    N = int( input())
    A = list( map( int, input().split()))
    CA = Counter(A)
    d = defaultdict( lambda : False)
    T = [False]*(10**6+1)
    A.sort()
    Z = [False]*(10**6+1)
    ans = 0
    for a in A:
        if CA[a] == 1 and not T[a]:
            ans += 1
        if not Z[a]:
            Z[a] = True
            for i in range(1, 10**6+1):
                if i*a > 10**6:
                    break
                T[i*a] = True
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,m=map(int,input().split())
for i in range(n,m+1):
  if m%i==0:
    print(m//i)
    exit()

### FIXED CODE ###

n,m=map(int,input().split())
for i in range(2,m):
  if i*i>m:
    print(1)
    exit()
  if m%i==0:
    break
for i in range(n,m+1):
  if m%i==0:
    print(m//i)
    exit()
### BUGGY CODE ###

import bisect
# N, M = 10, 3
# ARR = [1, 8, 5, 7, 100, 4, 52, 33, 13, 5]
# BRR = [
#     [3, 10],
#     [4, 30],
#     [1, 4]
# ]
N,M = map(int,input().split())
ARR = list(map(int,input().split()))
BRR = []
for i in range(M):
    BRR.append(list(map(int,input().split())))

def calculate(n, m, arr, brr):
    brr = sorted(brr, key=lambda x: -x[1])
    arr = sorted(arr)
    result = 0
    sIndex = 0
    for mIndex in range(m):
        br = brr[mIndex]
        kIndex = min(bisect.bisect_left(arr[sIndex:len(arr)],br[1]),br[0])
        if kIndex == 0:
            break
        result = result + kIndex*br[1]
        sIndex = sIndex + kIndex

    result = result + sum(arr[sIndex:len(arr)])

    print(result)

calculate(N, M, ARR, BRR)

### FIXED CODE ###

# N, M = 10, 3
# ARR = [1, 8, 5, 7, 100, 4, 52, 33, 13, 5]
# BRR = [
#     [3, 10],
#     [4, 30],
#     [1, 4]
# ]


N,M = map(int,input().split())
ARR = list(map(int,input().split()))
BRR = []
for i in range(M):
    BRR.append(list(map(int,input().split())))

def calculate(n, m, arr, brr):
    raw = []
    for ar in arr:
        raw.append([ar, 1])
    for br in brr:
        raw.append([br[1], br[0]])

    raw = sorted(raw,key=lambda x:-x[0])
    # print(raw)

    offset = 0
    sum = 0
    for ra in raw:
        if offset + ra[1] <= n:
            sum = sum + ra[1] * ra[0]
            offset = offset + ra[1]
        else:
            sum = sum + (n - offset) * ra[0]
            offset = n
            break
    print(sum)

calculate(N, M, ARR, BRR)
### BUGGY CODE ###

N, M = map(int, input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(int, input().split())
count = 0
for i in range(N):
	count += 1
	for j in range(M):
		if i+1 < L[j] or i+1 > R[j]:
			count -= 1
			break
print(count)

### FIXED CODE ###

N, M = map(int, input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(int, input().split())
s = 1
e = N
for i in range(M):
	if s < L[i]:
		s = L[i]
	if e > R[i]:
		e = R[i]
if s > e:
	print(0)
else:
	print(e-s+1)
### BUGGY CODE ###

from operator import itemgetter

n = input()
dishes = []
for i in range(int(n)):
    tmp = [int(each) for each in input().split()]
    dishes.append((tmp[0] - tmp[1], tmp[1] - tmp[0], tmp[0], tmp[1]))

dishes = [sorted(dishes, key=itemgetter(0, 2), reverse=True), sorted(dishes, key=itemgetter(0, 3), reverse=True)]

# print(dishes[0])
# print(dishes[1])

point = [0, 0]
player = 0
while len(dishes[0]) > 0:
    dish = dishes[player].pop(0)
    # if player == 0:
    #     dish = dishes.pop(0)
    # else:
    #     dish = dishes.pop(len(dishes) - 1)

    dishes[int(not player)].remove(dish)
    # print(dish)
    point[player] += dish[player + 2]
    player = int(not player)
    # print(point)
print(point[0] - point[1])


### FIXED CODE ###

n = input()
dishes = []
for i in range(int(n)):
    tmp = [int(each) for each in input().split()]
    dishes.append((abs(tmp[0] + tmp[1]), tmp[0], tmp[1]))

dishes = sorted(dishes, key=lambda x: x[0], reverse=True)

point = [0, 0]
player = 0
while len(dishes) > 0:
    dish = dishes.pop(0)
    point[player] += dish[player + 1]
    player = int(not player)
print(point[0] - point[1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,k=map(int, input().split()) 
a=list(map(int, input().split()))
mod=10**9+7
dp=[[0]*(k+1) for i in range(n+1)]

for i in range(n+1):
    dp[i][0]=1



for i in range(1,n+1):
    for j in range(1,k+1):
        if j-1-a[i-1]>=0:
            dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-a[i-1]]
            dp[i][j]%mod
        
        else:
            dp[i][j]=dp[i][j-1]+dp[i-1][j]   
            dp[i][j]%mod

print(dp[-1][-1]%mod)
    
    

### FIXED CODE ###

import sys
input = sys.stdin.readline

n,k=map(int, input().split()) 
a=list(map(int, input().split()))
mod=10**9+7
dp=[[0]*(k+1) for i in range(n+1)]

for i in range(n+1):
    dp[i][0]=1



for i in range(1,n+1):
    for j in range(1,k+1):
        if j-1-a[i-1]>=0:
            dp[i][j]=(dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-a[i-1]])%mod
        
        else:
            dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod

print(dp[-1][-1]%mod)
### BUGGY CODE ###

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

def solve():
    global K, S
    concat_S = S[:]
    while 'LL' in concat_S:
        concat_S = concat_S.replace('LL', 'L', 1)
    while 'RR' in concat_S:
        concat_S = concat_S.replace('RR', 'R', 1)

    ans = len(S) - len(concat_S)
    S = concat_S
    while K and len(S) > 3:
        S = ''.join([S[0], S[3:]])
        ans += 2
        K -= 1

    if K:
        if len(S) == 3:
            ans += 2
        elif len(S) == 2:
            ans += 1
        
    print(ans)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

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

def solve():
    global K, S
    concat_S = S[:]
    while 'LL' in concat_S:
        concat_S = concat_S.replace('LL', 'L')
    while 'RR' in concat_S:
        concat_S = concat_S.replace('RR', 'R')

    ans = len(S) - len(concat_S)
    if len(concat_S) >= 4:
        # 2個ずつ消す
        num_rm = min(K, (len(concat_S)-2)//2)
        K -= num_rm
        ans += num_rm * 2
        len_concat_S = len(S) - ans

        if K:
            if len_concat_S == 3:
                ans += 2
            elif len_concat_S == 2:
                ans += 1
        print(ans)
        return
    if K:
        if len(concat_S) == 3:
            ans += 2
        elif len(concat_S) == 2:
            ans += 1
        
    print(ans)
    return

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

def factorial(n):
    f=1
    for i in range(1,n+1):
        f*=i%(10**9+7)
    return f
n,m=map(int,input().split())
N=factorial(n)
if abs(n-m)>1:
    print(0)
elif abs(n-m)==0:
    print(2*N*N%(10**9+7))
elif n>m:
    print((N*N//n)%(10**9+7))
else:
    print(N*N*m%(10**9+7))


### FIXED CODE ###

n,m=map(int,input().split())
p=10**9+7
if abs(n-m)>=2:
    print(0)
elif n==m:
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%p
    print((2*ans*ans)%p)
else:
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%p
    for i in range(1,m+1):
        ans=(ans*i)%p
    print(ans%p)
### BUGGY CODE ###

n = int(input())
s = []

for _ in range(n):
    w = list(input())
    w.sort()
    s.append("".join(w))

count = 0

for i in range(n):
    for j in range(i+1, n):
        if s[i] == s[j]:
            count += 1

print(count)


### FIXED CODE ###

import collections

n = int(input())
s = []


def main():
    for _ in range(n):
        w = list(input())
        w.sort()
        s.append("".join(w))

    counter = collections.Counter(s)
    _, c = zip(*counter.most_common())

    ans = 0

    for num in c:
        if num == 1:
            return ans
        ans += num * (num-1) // 2

    return ans


print(main())
### BUGGY CODE ###

n = int(input())
ali = list(map(int,input().split()))

sumli = [0]
sum = 0
acum = 0

for i in ali:
    sum = sum + i
    sumli.append(sum)

sumtally =[sumli.count(x) for x in set(sumli)]

for j in sumtally:
    acum = acum+(j*(j-1))//2

print(acum)


### FIXED CODE ###

from collections import Counter

n = int(input())
ali = list(map(int,input().split()))

sumli = [0]
sum = 0
acum = 0

for i in ali:
    sum = sum + i
    sumli.append(sum)

sumc = Counter(sumli)

for j in list(sumc):
    acum = acum+(sumc[j]*(sumc[j]-1))//2

print(acum)