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

"""
1. マス同士は有効グラフの一本道になっている。で、必ずどこかでループが発生している。

2. 各点から各点に移動する場合のスコアの合計とステップ数(ループ内の場合は一周以内のもの)を前処理(dfs)で求めておく。dp[i][j] => iからjまでのスコアとステップ数

3. K > N の場合、ループを通るとスコアがマイナスになるなら（dp[i][i]がマイナスになるようなiが存在するなら）、ループを一周しない方がよい。
ループを通るとスコアがプラスになるなら、

各iに対して地点iからスタートする場合というのをシミュレートすると実装が楽そう。
K <= Nの場合はi番目からスタートして、dfsでstep数がKに到達するまで進み続けて、スコアの最大値を図る。
Kが大きい場合は、dfsで道をたどっていってループを検出したら、その時点でループスコアがマイナスかプラスかを判断して、マイナスなら終了。
プラスならループスコア*(K//ループstep)を加算してできる限りKを減らす。そこからstep数がKに到達するまでdfsで道をたどっていって最大値を求める。
各スタート地点ごとにO(N)で処理可能なので、全体ではO(N^2)で処理できる
"""
import sys
sys.setrecursionlimit(10000)
def main():
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    C = list(map(int,input().split()))

    def dfs(cur,score,scores,step,steps):
        if scores[cur] == None:
            scores[cur] = score
            steps[cur] = step
        else:
            if scores[cur] >= score:
                return
            else:
                loopStep = step - steps[cur]
                loopScore = score - scores[cur]

                scores[cur] = score
                steps[cur] = step

                scores[cur] += ((K - steps[cur])//loopStep)*loopScore
                steps[cur] += ((K - steps[cur])//loopStep)*loopStep
                
        if steps[cur] < K:
            p = P[cur-1]
            c = C[p-1]
            dfs(p,scores[cur]+c,scores,steps[cur]+1,steps)
        else:
            return

    ans = -float("INF")
    for i in range(1,N+1):
        scores = [None]*(N+1)
        steps = [None]*(N+1)
        dfs(i,0,scores,0,steps)
        for j in range(N+1):
            if scores[j] != None and steps[j] != 0:
                ans = max(ans,scores[j])
    print(ans)
main()

### FIXED CODE ###

"""
1. マス同士は有効グラフの一本道になっている。で、必ずどこかでループが発生している。

2. 各点から各点に移動する場合のスコアの合計とステップ数(ループ内の場合は一周以内のもの)を前処理(dfs)で求めておく。dp[i][j] => iからjまでのスコアとステップ数

3. K > N の場合、ループを通るとスコアがマイナスになるなら（dp[i][i]がマイナスになるようなiが存在するなら）、ループを一周しない方がよい。
ループを通るとスコアがプラスになるなら、

各iに対して地点iからスタートする場合というのをシミュレートすると実装が楽そう。
K <= Nの場合はi番目からスタートして、dfsでstep数がKに到達するまで進み続けて、スコアの最大値を図る。
Kが大きい場合は、dfsで道をたどっていってループを検出したら、その時点でループスコアがマイナスかプラスかを判断して、マイナスなら終了。
プラスならループスコア*(K//ループstep)を加算してできる限りKを減らす。そこからstep数がKに到達するまでdfsで道をたどっていって最大値を求める。
各スタート地点ごとにO(N)で処理可能なので、全体ではO(N^2)で処理できる
"""
N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

ans = -float("INF")

for i in range(1,N+1):
    scores = [None]*(N+1)
    steps = [None]*(N+1)
    cur = i
    score = 0
    step = 0
    loopFlag = False
    while step <= K:
        if scores[cur]!=None and not loopFlag:
            loopFlag = True
            loopScore = score - scores[cur]
            loopStep = step - steps[cur]
            ans = max(ans,score)
            restLoop = (K-step)//loopStep
            if restLoop > 0:
                restLoop -= 1
            score += restLoop*loopScore
            step += restLoop*loopStep
        scores[cur] = score
        steps[cur] = step
        if step != 0:
            ans = max(ans,score)
        p = P[cur-1]
        c = C[p-1]
        cur = p
        score += c
        step += 1

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

#14:05
n = int(input())
krus = []
raw = []
for i in range(n):
  tmp = list(map(int,input().split()))
  raw.append(tmp)
  for j in range(n):
    krus.append([tmp[j],i,j])
krus.sort()
#print(krus)
ans = 0
inf = 10 ** 18
wf = [[inf for _ in range(n)] for _ in range(n)]
for x in krus:
  d,i,j = x
  if wf[i][j] < d:
    print(-1)
    exit()
  elif wf[i][j] == d:
    continue
  wf[i][j] = d
  ans += d
  for a in range(n):
    for b in range(n):
      wf[a][b] = min(wf[a][b], wf[a][i] + d + wf[j][b])
      wf[b][a] = min(wf[b][a], wf[b][i] + d + wf[j][a])
  #print(wf)
  #print(x)
print(ans//2)

### FIXED CODE ###

n = int(input())
wf = []
for _ in range(n):
  wf.append(list(map(int,input().split())))
cnt = [[0 for _ in range(n)] for _ in range(n)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      if wf[i][j] > wf[i][k] + wf[k][j]:
        print(-1)
        exit()
      elif wf[i][j] == wf[i][k] + wf[k][j]:
        cnt[i][j] += 1
#print(cnt)
ans = 0
for i in range(n):
  for j in range(n):
    if cnt[i][j] <= 2:
      ans += wf[i][j]
print(ans//2)
### BUGGY CODE ###

S = input()
Q = int(input())
a = [0]*Q
for i in range(0, Q):
    a[i] = list(input().split())
    if a[i][0] == "1":
        S = S[::-1]
    elif a[i][1] == "1":
        S = a[i][2]+S
    else:
        S = S+a[i][2]
print (S)

### FIXED CODE ###

import collections

S = collections.deque(list(input()))
Q = int(input())
rev = 0
for i in range(0, Q):
    query = list(input().split())
    if query[0] == "1":
        rev = rev+1
    else:
        if query[1] == "1":
            if rev%2 == 0:
                S.appendleft(query[2])
            else:
                S.append(query[2])
        else:
            if rev%2 == 0:
                S.append(query[2])
            else:
                S.appendleft(query[2])
if rev%2 == 0:
    for i in S:
        print (i, end = "")
else:
    for i in reversed(S):
        print (i, end = "")
### BUGGY CODE ###

from  math import gcd
n = int(input())
a = sorted(list(map(int,input().split())))

l = []
l.append(a[0])
cou =[]
for i in range(1,n):
    b = a[i]
    for j in range(len(l)):
      if b==l[j]:
        cou.append(b)
      if b%l[j]==0:
          break
    else:
        l.append(b)
print(len(l)-len(set(cou)))

### FIXED CODE ###

counter = [0 for i in range(10**6+1)]
n = int(input())
a = sorted(list(map(int,input().split())))
for i in a:
  counter[i] += 1
l  = [0 for i in range(10**6+1)]
cou = 0
for i in range(n):
  b = a[i]
  if l[b]==0:
    cou += 1
    for j in range(b,10**6+1,b):
      l[j] = 1
    if counter[b]>=2:
      cou -=1
print(cou)
### BUGGY CODE ###


X = int(input())
now_money=100
i = 0
t= 100

while X >= now_money:
    t += t
    i += 1
print(i)

### FIXED CODE ###

X=int(input())
i=100
year=0
while i<X:
  i+=i//100
  year+=1
print(year)
### BUGGY CODE ###

import math

k = int(input())
ans = 0

for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans += math.gcd(math.gcd(a, b), c)

print(ans)


### FIXED CODE ###

import math

k = int(input())
ans = 0

for a in range(1,k-1):
    for b in range(a+1,k):
        for c in range(b+1,k+1):
            ans += math.gcd(math.gcd(a, b), c)*6

for a in range(1,k):
    for b in range(a+1,k+1):
        ans += math.gcd(a,b)*6

for a in range(1,k+1):
    ans += a

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

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

ans = 0
for i in range(N-2):
    for j in range(i, N-1):
        for k in range(j, N):
            if len({S[i], S[j], S[k]}) == 3:
                if (j - i) != (k - j):
                    ans += 1                

print(ans)

### FIXED CODE ###

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

smap = {
    'R': 0,
    'G': 1,
    'B': 2,
}

def get_t(a, b):
    a, b = smap[a], smap[b]
    if a + b == 1:
        return 2
    elif a + b == 3:
        return 0
    else:
        return 1

d = [[0 for _ in range(3)] for _ in range(N)]

for i in range(N):
    for j in range(N):
        if i < j:
            s = S[j]
            d[i][smap[s]] += 1

ans = 0
for j in range(1, N-1):
    c = S[j]
    for i in range(0, j):        
        l = S[i]
        if c == l:
            continue
        t = get_t(c, l)
            
        if j + j - i < N and smap[S[j + (j - i)]] == t:
            ans -= 1
        ans += d[j][t]

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

R, G, B, N = map(int, input().split())
ans = 0
for r in range(N//R+1):
    for g in range((N-r*R)//G+1):
        if N-r*R-g*G >= 0 and (N-r*R-g*G) % B == 0:
            ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(N//R+1):
    for g in range((N-r*R)//G+1):
        if (N-r*R-g*G) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
    s = str(input())
    S.append(s)

T = list(set(S))
t = 1
U = []
for i in range(len(T)):
    if t < S.count(T[i]):
        t = S.count(T[i])
        U = [T[i]]
    elif t == S.count(T[i]):
        U.append(T[i])

U_ = list(sorted(U))
for i in range(len(U_)):
    print(U_[i])

### FIXED CODE ###

N = int(input())
dic = {}
for i in range(N):
    s = str(input())
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

S = sorted(dic.values())
t = S[-1]

X = []
for key in dic:
    if dic[key] == t:
        X.append(key)
x = sorted(X)

for i in range(len(X)):
    print(x[i])
### BUGGY CODE ###

N = int(input())
A = [int(n) for n in input().split(' ')]
s = 0
for i in range(N-1):
    for j in range(i, N):
        xor = A[i]^A[j]
        s += xor
    
ans = s % (10**9+7)
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(n) for n in input().split(' ')]
 
ans = 0
for i in range(60):
    x = 0
    for A_i in A:
        if A_i>>i&1:
            x += 1
    ans += x*(N-x)*2**i
ans = ans % (10**9+7)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod = 10**9+7
n, k = map(int, input().split())
A = tuple(tuple(map(int, input().split())) for _ in range(n))
def matmul(X, Y):
  Z = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        Z[i][j] += X[i][k] * Y[k][j]
        Z[i][j] %= mod
  return Z
  
def matpow(k):
  if k == 1:
    return A
  if k%2:
    return matmul(A, matpow(k-1))
  X = matpow(k//2)
  return matmul(X, X)

B = matpow(k)
ans = 0
for i in range(n):
  for j in range(n):
    ans += B[i][j]
    ans %= mod
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 10**9+7
n, k = map(int, input().split())
A = tuple(tuple(map(int, input().split())) for _ in range(n))
def matmul(X, Y):
  Z = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        Z[i][j] += X[i][k] * Y[k][j]
        Z[i][j] %= mod
  return Z
  
def matpow(k):
  if k == 1:
    return A
  if k%2:
    return matmul(A, matpow(k-1))
  X = matpow(k//2)
  return matmul(X, X)

B = matpow(k)
ans = 0
for i in range(n):
  for j in range(n):
    ans += B[i][j]
    ans %= mod
print(ans)
### BUGGY CODE ###

from sys import stdin

# stdin = open("testdata.txt", "r")

def input():
	return stdin.readline().strip()

from collections import deque

n, m = map(int, input().split())

s = input()

def bfs(src):
	que = deque([[src, []]])
	visited = {src, }

	while que:
		u, path = que.popleft()
		if u == n:
			return path
		for i in range(1, m+1):
			next_pos = u + i
			if next_pos not in visited and next_pos <= n and s[next_pos]=='0':
				visited.add(next_pos)
				que.append((next_pos, path+[i]))
	return -1

ans = bfs(0)
if ans == -1:
	print(ans)
else:
	print(*ans)

### FIXED CODE ###

N, M = map(int, input().split())
S = input().strip()
T = S[::-1]

l = []
i = 0
while i < N:
  t = T[i+1: i+M+1][::-1]
  if '0' not in t:
    print(-1)
    exit()
  else:
    x = min(M - t.index('0'), len(t))
    l.append(x)
    i += x
print(*l[::-1])
### BUGGY CODE ###

n, yen = map(int, input().split())
for x in range(n+1):
    for y in range(n+1):
        zz = yen - (10000*x + 5000*y)
        if zz%1000 != 0:
            continue
        z = int(zz / 1000)
        if z < 0:
            continue
        if x + y + z == n:
            print('{} {} {}'.format(x, y, z))
            exit()
else:
    print('-1 -1 -1')


### FIXED CODE ###

n, Y = map(int, input().split())
ntx = n * 10000
nty = n * 5000
ntz = n * 1000
ans = []
if Y > ntx or ntz > Y:
    ans = [-1, -1, -1]
elif ntx == Y:
    ans = [n, 0, 0]
elif nty == Y:
    ans = [0, n, 0]
elif ntz == Y:
    ans = [0, 0, n]
elif ntx > Y > nty:
    x = 0
    y = n
    z = 0
    for i in range(1, n+1):
        y = n - i
        x = i
        for j in range(0, i+1):
            x = j
            z = i - j
            if 10000*x + 5000*y + 1000*z == Y:
                ans = [x, y, z]
elif nty > Y > ntz:
    x = 0
    y = 0
    z = n
    for i in range(1, n+1):
        z = n - i
        x = i
        for j in range(0, i+1):
            x = j
            y = i - j
            if 10000*x + 5000*y + 1000*z == Y:
                ans = [x, y, z]
if len(ans) == 0:
    ans = [-1, -1, -1]
print(' '.join(map(str, ans)))
### BUGGY CODE ###

n=int(input())
ans=0
hoge=list(map(int,input().split()))
for i in range(100000):
  if(hoge.count(i-1)+hoge.count(i)+hoge.count(i+1)>=ans):
    ans=hoge.count(i-1)+hoge.count(i)+hoge.count(i+1)
    
print(ans)

### FIXED CODE ###

n=int(input())
hoge=list(map(int,input().split()))
huga=[0]*(10**5+1)
for i in hoge:
  if(i==10**5):
    huga[i-1]+=1
    huga[i]+=1
  elif(i==0):
    huga[i]+=1
    huga[i+1]+=1
  else:
    huga[i-1]+=1
    huga[i]+=1
    huga[i+1]+=1
print(max(huga))
### BUGGY CODE ###

L,R = map(int,input().split())
ans = R*R
for i in range(L,R+1):
    for j in range(i+1,R+1):
        ans = min(ans,(i*j)%2019)
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())
if R - L >= 2019:
    ans = 0
else:
    ans = R*R
    for i in range(L,R+1):
        for j in range(i+1,R+1):
            ans = min(ans,(i*j)%2019)
print(ans)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    S = input()[::-1]
    L = len(S)
    dp = [0] * 2019
    wk = 0
    r = 1
    for i in range(L):
        wk += int(S[i])*r
        wk %= 2019
        r *= 10
        dp[wk] += 1
    ret = dp[0]
    for i in range(2019):
        ret += dp[i]*(dp[i]-1)//2
    print(ret)


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    S = input()[::-1]
    L = len(S)
    dp = [0] * 2019
    wk = 0
    r = 1
    for i in range(L):
        wk += int(S[i])*r
        wk %= 2019
        r *= 10
        r %= 2019
        dp[wk] += 1
    ret = dp[0]
    for i in range(2019):
        ret += dp[i]*(dp[i]-1)//2
    print(ret)


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

#!/usr/bin/python3
# -*- coding:utf-8 -*-

from copy import deepcopy

def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return
  
  remains = [0] * (n+1)
  for r in range(n-1, -1, -1):
    remain = (int(s[r]) * (10 ** ((n-1)-r))) % p
    remains[r] = (remains[r+1] + remain) % p
  
  remains = [0]
  for r in range(n):
    remains.append(int(s[-(r+1):]) % p)
  remains.reverse()
  
  counts = [0] * p
  for remain in remains:
    counts[remain] += 1
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return
  
  remains = [0] * (n+1)
  counts = [0] * p
  counts[0] += 1
  x = 1
  for r in range(n):
    remain = (int(s[-(r+1)]) * x) % p
    remains[-(r+1)] = (remains[-r] + remain) % p
    counts[remains[-(r+1)]] += 1
    x = (x * 10) % p
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)

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

N = int(input())
x = [i for i in map(int ,input().split())]
mid = (N-1) // 2
for i in range(N):
    tmp = x[:]
    tmp.remove(x[i])
    tmp.sort()
    print(tmp[mid])

### FIXED CODE ###

N = int(input())
x = [i for i in map(int ,input().split())]
mid = N // 2
tmp = x[:]
tmp.sort()
for i in range(N):
    if tmp[mid] <= x[i]:
        print(tmp[mid-1])
    else:
        print(tmp[mid])
### BUGGY CODE ###

N,H=list(map(int,input().split()))
a=[0]*N
b=[0]*N

for i in range(N):
    ta,tb=list(map(int,input().split()))
    a[i]=ta
    b[i]=tb

amax=max(a)
b.sort(reverse=True)

res=10**10

for i in range(N+1):
    cnt=i
    ch=H

    ch-=sum(b[:i]) if i>0 else 0
    if H>0:
        cnt+=(ch+amax-1)//amax

    res=min(res,cnt)

print(res)    


### FIXED CODE ###

N,H=list(map(int,input().split()))
a=[0]*N
b=[0]*N

for i in range(N):
    ta,tb=list(map(int,input().split()))
    a[i]=ta
    b[i]=tb

amax=max(a)
b.sort(reverse=True)

res=10**10
csum=0
for i in range(N+1):
    cnt=i
    ch=H
    csum+=b[i-1] if i>0 else 0
    ch-=csum

    if ch>0:
        cnt+=-(-ch//amax)

    res=min(res,cnt)

print(res)
### BUGGY CODE ###

from numba import njit, int32, int64
from numba.typed import Dict

@njit
def solve(B):
    A = Dict.empty(
        key_type=int64,
        value_type=int64)
    for b in B:
      A[b] = A.get(b, 0) + 1
    r = 0
    for a, v in A.items():
        if v > 1:
            continue
        if a > 1 and 1 in A:
            continue
        i = 2
        while i * i <= a:
            if a % i == 0:
                if i in A:
                    break
                if a // i in A:
                    break
            i += 1
        else:
            r += 1
    return r

def main():
    N = int(input())
    A = list(map(int, input().split()))
    return solve(A)

print(main())



### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    dp = [False] * (A[-1] + 1)
    r = 0

    for i, a in enumerate(A):
        if dp[a]:
            continue
        dp[a::a] = [True] * len(dp[a::a])
        if i < N - 1 and A[i + 1] == a:
            continue
        r += 1
    return r


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

import itertools

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

count = 0
for x in range(0,K + 1):
    for y,z in itertools.product(range(0,K + 1),range(0,K + 1)):
        if x + y + z == S:
            count += 1

print(count)

### FIXED CODE ###

import itertools
    
K, S = map(int,input().split())

count = 0
for x,y in itertools.product(range(0,K + 1),range(0,K + 1)):
    z = S - x - y
    if 0 <= z <= K:
        count += 1

print(count)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=sorted([x for x in set(a) if a.count(x)>1], key=a.index)
c=[a.count(i) for i in b]
ans=0
for i in c:
    ans+=((i-1)*i)//2

cnt=ans   
for i in range(n):
   if a[i] in b:
       ans-=(c[b.index(a[i])]-1)
       print(ans)
       ans=cnt
   else:
       print(ans)

### FIXED CODE ###

N = int(input())
A = [int(a)-1 for a in input().split()]
X = [0] * N
for a in A:
    X[a] += 1
s = 0
for x in X:
    s += x * (x-1) // 2

for a in A:
    print(s - (X[a] - 1))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

count = 0
for i in range((N // R) + 1):
    for j in range(((N - i * R) // G) + 1):
        for k in range(((N - i * R - j * G) // B) + 1):
            if i * R + j * G + k * B == N:
                count += 1

print(count)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

count = 0
for i in range((N // R) + 1):
    ir = i * R
    for j in range(((N - ir) // G) + 1):
        jg = j * G
        k = (N - ir - jg) / B
        if k.is_integer():
            count += 1

print(count)
### BUGGY CODE ###

# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    N = ir()
    P = lr()
    P = [((p-1)//N, (p-1)%N) for p in P]
    dp = [[min(i, N-1-i)] * N for i in range(N)]
    people = [[True] * N for i in range(N)]
    for j in range(N):
        x = min(j, N-1-j)
        for i in range(N):
            dp[i][j] = min(dp[i][j], x)

    answer = 0
    for i, j in P:
        answer += dp[i][j]
        people[i][j] = False
        que = deque([(i, j, dp[i][j])])
        popleft = que.popleft; append = que.append
        while que:
            y, x, cur = popleft()
            cur += people[y][x]
            if x > 0:
                if dp[y][x-1] > cur:
                    dp[y][x-1] = cur
                    append((y, x-1, cur))
            if x < N-1:
                if dp[y][x+1] > cur:
                    dp[y][x+1] = cur
                    append((y, x+1, cur))
            if y > 0:
                if dp[y-1][x] > cur:
                    dp[y-1][x] = cur
                    append((y-1, x, cur))
            if y < N-1:
                if dp[y+1][x] > cur:
                    dp[y+1][x] = cur
                    append((y+1, x, cur))

    print(answer)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding: utf-8
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    N = ir()
    P = lr()
    P = [((p-1)//N, (p-1)%N) for p in P]
    dp = [[min(i, N-1-i, j, N-1-j) for j in range(N)] for i in range(N)]
    people = [[True] * N for i in range(N)]

    answer = 0
    for i, j in P:
        answer += dp[i][j]
        people[i][j] = False
        que = deque([(i, j, dp[i][j])])
        popleft = que.popleft; append = que.append
        while que:
            y, x, cur = popleft()
            cur += people[y][x]
            if x > 0:
                if dp[y][x-1] > cur:
                    dp[y][x-1] = cur
                    append((y, x-1, cur))
            if x < N-1:
                if dp[y][x+1] > cur:
                    dp[y][x+1] = cur
                    append((y, x+1, cur))
            if y > 0:
                if dp[y-1][x] > cur:
                    dp[y-1][x] = cur
                    append((y-1, x, cur))
            if y < N-1:
                if dp[y+1][x] > cur:
                    dp[y+1][x] = cur
                    append((y+1, x, cur))

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

n, q = map(int, input().split())
s = input()
x = [tuple(input().split()) for _ in range(q)]

l = 0
r = n
while r-l > 1:
    m = (l+r)//2
    c = s[m]
    idx = m
    for j in range(q):
        if x[j][0] == c:
            if idx == 0 and x[j][1] == "L":
                l = m
                break
            elif idx == n-1 and x[j][1] == "R":
                r = m
                break
            else:
                if x[j][1] == "L":
                    c = s[idx-1]
                    idx -= 1
                else:
                    c = s[idx+1]
                    idx += 1

        if j == q-1:
            r = m
idx1 = l

l = 0
r = n
while r-l > 1:
    m = (l+r)//2
    c = s[m]
    idx = m
    for j in range(q):
        if x[j][0] == c:
            if idx == 0 and x[j][1] == "L":
                l = m
                break
            elif idx == n-1 and x[j][1] == "R":
                r = m
                break
            else:
                if x[j][1] == "L":
                    c = s[idx-1]
                    idx -= 1
                else:
                    c = s[idx+1]
                    idx += 1

        if j == q-1:
            l = m
idx2 = r
print(n-(idx1+1)-(n-idx2))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
x = [tuple(input().split()) for _ in range(q)]

l = 0
r = n
while r-l > 1:
    m = (l+r)//2
    c = s[m]
    idx = m
    for j in range(q):
        if x[j][0] == c:
            if idx == 0 and x[j][1] == "L":
                l = m
                break
            elif idx == n-1 and x[j][1] == "R":
                r = m
                break
            else:
                if x[j][1] == "L":
                    c = s[idx-1]
                    idx -= 1
                else:
                    c = s[idx+1]
                    idx += 1

        if j == q-1:
            r = m
idx1 = l

l = 0
r = n
while r-l > 1:
    m = (l+r)//2
    c = s[m]
    idx = m
    for j in range(q):
        if x[j][0] == c:
            if idx == 0 and x[j][1] == "L":
                l = m
                break
            elif idx == n-1 and x[j][1] == "R":
                r = m
                break
            else:
                if x[j][1] == "L":
                    c = s[idx-1]
                    idx -= 1
                else:
                    c = s[idx+1]
                    idx += 1

        if j == q-1:
            l = m
idx2 = r
print(n-(idx1+1)-(n-idx2))