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

import heapq

def check(h, T, A, B):
    # T回の爆破でいける？ -> BがT回行われる下で、残ったモンスターをT回のA - Bダメ攻撃で倒せる？
    que = []
    for hi in h:
        if hi - B * T > 0:
            que.append(- hi + B * T)
    que.sort()
    A_count = 0
    for q in que:
        count = (-q + (A - B) - 1) // (A - B)
        A_count += count
    
    return A_count <= T


N, A, B = map(int, input().split(" "))
h = []
for _ in range(N):
    h.append(int(input()))

lower, upper = 0, 10 ** 15

while upper - lower > 1:
    mid = (upper + lower) // 2
    if check(h, mid, A, B):
        upper = mid
    else:
        lower = mid

print(upper)

### FIXED CODE ###

import heapq

def check(h, T, A, B):
    # T回の爆破でいける？ -> BがT回行われる下で、残ったモンスターをT回のA - Bダメ攻撃で倒せる？
    que = []
    for hi in h:
        if hi - B * T > 0:
            que.append(- hi + B * T)
    que.sort()
    A_count = 0
    for q in que:
        count = (-q + (A - B) - 1) // (A - B)
        A_count += count
    
    return A_count <= T


N, A, B = map(int, input().split(" "))
h = []
for _ in range(N):
    h.append(int(input()))

lower, upper = 0, 10 ** 15

while upper - lower > 1:
    mid = (upper + lower) // 2
    if check(h, mid, A, B):
        upper = mid
    else:
        lower = mid

print(upper)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

def main():
    N = int(input())
    memo = []
    base = 0
    for i in range(N-1):
        memo.append(base)
        base += N-i-1
    edge = [[] for _ in range((N*(N-1))//2)]
    
    for i in range(N):
        a = list(map(int,input().split()))
        b = []
        for j in a:
            j -= 1
            if i < j:
                b.append(memo[i]+j-i-1)
            else:
                b.append(memo[j]+i-j-1)
        for i in range(N-2):
            edge[b[i+1]].append(b[i])

    go = [False]*((N*(N-1))//2)
    cul = [False]*((N*(N-1))//2)
    dp = [0]*((N*(N-1))//2)
    
    def dfs(v):
        if go[v]:
            if not cul[v]:
                return -1
            return dp[v]
        go[v] = True
        dp[v] = 1
        for u in edge[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v],ret+1)
        cul[v] = True
        return dp[v]
    
    ans = 0
    for i in range((N*(N-1))//2):
        ret = dfs(i)
        if ret == -1:
            print(-1)
            exit()
        ans = max(ans,ret)
        
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

def main():
    N = int(input())
    memo = []
    base = 0
    for i in range(N-1):
        memo.append(base)
        base += N-i-1
    edge = [[] for _ in range((N*(N-1))//2)]
    
    for i in range(N):
        a = list(map(int,input().split()))
        b = []
        for j in a:
            j -= 1
            if i < j:
                b.append(memo[i]+j-i-1)
            else:
                b.append(memo[j]+i-j-1)
        for i in range(N-2):
            edge[b[i+1]].append(b[i])

    go = [False]*((N*(N-1))//2)
    cul = [False]*((N*(N-1))//2)
    dp = [0]*((N*(N-1))//2)
    
    def dfs(v):
        if go[v]:
            if not cul[v]:
                return -1
            return dp[v]
        go[v] = True
        dp[v] = 1
        for u in edge[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v],ret+1)
        cul[v] = True
        return dp[v]
    
    ans = 0
    for i in range((N*(N-1))//2):
        ret = dfs(i)
        if ret == -1:
            print(-1)
            exit()
        ans = max(ans,ret)
        
    print(ans)

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

import sys,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n = onem()

a = l()

b = l()

t = []

for i in range(n):
    if b[i] != a[i]:
        hq.heappush(t,(-b[i],i))
co = 0
while t:
    k = hq.heappop(t)
    k = (-k[0],k[1])
    q,w = divmod(k[0] - a[k[1]], b[(k[1] - 1) % n] + b[(k[1] + 1) % n])
    co += q
    if q == 0:
        print(-1)
        exit()
    w = a[k[1]] + w
    b[k[1]] = w
    if b[k[1]] != a[k[1]]:
        hq.heappush(t,(-w,k[1]))

print(co)

### FIXED CODE ###

import heapq as hq
mod = 10**9+7
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())

def onon():
    n = onem()

    a = l()

    b = l()

    t = []

    for i in range(n):
        if b[i] != a[i]:
            hq.heappush(t,(-b[i],i))
    co = 0
    while t:
        k = hq.heappop(t)
        k = (-k[0],k[1])
        q,w = divmod(k[0] - a[k[1]], b[(k[1] - 1) % n] + b[(k[1] + 1) % n])
        co += q
        if q == 0:
            return -1
        w = a[k[1]] + w
        b[k[1]] = w
        if b[k[1]] != a[k[1]]:
            hq.heappush(t,(-w,k[1]))
    return co
print(onon())
### BUGGY CODE ###


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

if(0 in a):
    print("0")
    exit()

for i in range(int(n)):
    ans *= a[i]

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

### FIXED CODE ###

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

if(0 in a):
    print("0")
    exit()

for i in range(int(n)):
    ans *= a[i]
    if(ans>10**18):
        print("-1")
        exit()

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

from fractions import gcd
import  copy
N = int(input())
A = list(map(int,input().split()))
B = copy.deepcopy(A)
gcdlist = []
for i in range(N):
    del B[i]
    ans = B[0]
    for k in range(1,len(B)):
        ans = gcd(ans,B[k])
    gcdlist.append(ans)
    B = copy.deepcopy(A)
print(max(gcdlist))

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
top = [0]*(N+1)
bot = [0]*(N+1)
for i in range(N):
    top[i+1] = gcd(top[i],A[i])
    bot[N-i-1]= gcd(bot[N-i],A[N-i-1])
# print(top,bot)
ans = 0
for i in range(N):
    # print(gcd(top[i], bot[i + 1]))
    ans = max(ans,gcd(top[i],bot[i+1]))
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
diff = abs(n-m)
count1 = 1
count2 = 1
def saiki(n):
    if n<=1:
        return 1
    return n * saiki(n-1)
if diff >= 2:
    print(0)
elif diff == 1:
    for i in range(1,max(n,m)+1):
        count1 *= i
    for i in range(1,(min(n,m)+1)):
        count2 *= i
    print(count1*count2%(10**9+7))
else:
    for i in range(1,n+1):
        count1 *= i
    print(count1*count1*2%(10**9+7))


### FIXED CODE ###

import math
n,m = map(int,input().split())
diff = abs(n-m)
count1 = 1
count2 = 1
a = 1

if diff >= 2:
    print(0)
elif diff == 1:
    ans = math.factorial(max(n,m))
    print(ans*(ans//max(n,m))%(10**9+7))
else:
    ans = math.factorial(n)
    print(ans*ans*2%(10**9+7))
### BUGGY CODE ###

N, K = map(int, input().split())
dp = [float('inf') for _ in range(N)]
h = list(map(int, input().split()))
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2, N):
    for k in range(1,min(K, i)+1):
        dp[i] = min(dp[i], dp[i-k]+abs(h[i]-h[i-k]))
print(dp[-1])

### FIXED CODE ###

N,K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')]*len(h)
dp[0] = 0
for i in range(N):
    if i<N-K:
        for k in range(1,K+1):
            dp[i+k] = min(dp[i]+abs(h[i]-h[i+k]), dp[i+k])
    else:
        for k in range(1, N-i):
            dp[i+k] = min(dp[i]+abs(h[i]-h[i+k]), dp[i+k])
print(dp[-1])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def dfs(v=0, c=0):
    if visited[v] is True:
        return
    visited[v] = True
    c += counter[v]
    ans[v] = c
    for nv in edge[v]:
        if visited[nv] is True:
            continue
        dfs(nv, c)
    return


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {k: 0 for k in range(N)}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] += q

ans = [0 for i in range(N)]
visited = [False for i in range(N)]

dfs()

print(" ".join(list(map(str, ans))))


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def bfs():
    visited[0] = True
    ans[0] = counter[0]
    deq = deque()
    deq.append(0)
    while deq:
        v = deq.popleft()
        for nv in edge[v]:
            if visited[nv] is True:
                continue
            visited[nv] = True
            ans[nv] = ans[v] + counter[nv]
            deq.append(nv)


N, Q = inpl()

edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = inpl()
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

counter = {k: 0 for k in range(N)}
for i in range(Q):
    p, q = inpl()
    counter[p - 1] = counter.get(p - 1, 0) + q

ans = [0 for i in range(N)]
visited = [False for i in range(N)]

bfs()

print(" ".join(list(map(str, ans))))
### BUGGY CODE ###

import sys
s0,t0=input(),input()
s,t=list(s0),list(t0)
n=len(s)
sn=set(s)
tn=set(t)
if len(sn)!=len(tn) or len(s)!=len(t):
  print('No')
  sys.exit()
for i in range(n):
  if s0[i]!=t0[i]:
    s_tmp=s0[i]
    t_tmp=t0[i]
    s0=s0.replace(s0[i],'0').replace(t0[i],'1').replace('0',t_tmp).replace('1',s_tmp)
if s0==t0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import sys
s0,t0=input(),input()
s,t=list(s0),list(t0)
n=len(s)
sn=set(s)
tn=set(t)
if len(sn)!=len(tn) or len(s)!=len(t):
  print('No')
  sys.exit()
for i in range(n):
  if s[i]!=t[i]:
    if s.index(s[i])!=t.index(t[i]):
      print('No')
      sys.exit()
print('Yes')
### BUGGY CODE ###

import math
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += math.gcd(k, math.gcd(i,j))
print(ans)

### FIXED CODE ###

K = int(input())
# K = 2
import math
import itertools

def better_gcd(a,b,c):
    tup = set((a,b,c))
    kinds = len(tup)
    if kinds == 3:
        return math.gcd(a, math.gcd(b, c)) * 6
    elif kinds == 2:
        return math.gcd(*tup) * 3
    else:
        return a

ans = 0
cands = list(itertools.combinations_with_replacement(range(1,K+1), 3))
for c in cands:
    ans += better_gcd(*c)
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
K = 60

ans = 0
mod = 10 ** 9 + 7
power = 1

for i in range(K):
    bit = sum(A >> i & 1)
    ans += power * (bit * (N - bit))
    power *= 2
    power %= mod

print(ans % mod)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

K = len(bin(np.max(A))) - 2

ans = 0
mod = 10 ** 9 + 7
N %= mod

for i in range(K):
    bit = np.count_nonzero(A >> i & 1) % mod
    ans += 2 ** i * bit * (N - bit)
    ans %= mod
    
print(ans)
### BUGGY CODE ###

from numpy import gcd 
k = int(input())
sss = 0
for a in range(1,k+1):
    for b in range(a+1,k+1):
        tmp = gcd(a,b)
        sss += 6*tmp
        for c in range(b+1,k+1):
            sss += 6*gcd(tmp,c)
sss += k*(k+1)//2
print(sss)

### FIXED CODE ###

from math import gcd 
k = int(input())
sss = 0
for a in range(1,k+1):
    for b in range(a+1,k+1):
        tmp = gcd(a,b)
        sss += 6*tmp
        for c in range(b+1,k+1):
            sss += 6*gcd(tmp,c)
sss += k*(k+1)//2
print(sss)
### BUGGY CODE ###

while 1:
    n,s=map(int,input().split())
    if not n:break
    a=sorted([int(input()) for _ in range(n)],reverse=1)
    b=0
    for i in range(n):
        try:
            for j in range(i+1,n):
                if a[i]+a[j]>s:b+=1
                else:raise Exception;break
        except:break
    print(b)

### FIXED CODE ###

while 1:
    n,s=map(int,input().split())
    if n==0:break
    r=[0]*101
    for _ in [0]*n:r[int(input())]+=1
    a=0
    for i in range(101):
        if i*2>s:a+=(r[i]**2-r[i])//2
        a+=r[i]*sum(r[j] for j in range(max(i+1,s+1-i),101))
    print(a)
### BUGGY CODE ###

import collections

n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt = collections.Counter(a)
ans = 0
if len(cnt.most_common()) <= k:
    print(0)
    exit()
for i in range(k):
    ans += cnt.most_common()[i][1]
print(n - ans)

### FIXED CODE ###

import collections

n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt = collections.Counter(a)
ans = 0
t=cnt.most_common()
if len(t) <= k:
    print(0)
    exit()

for i in range(k):
    ans += t[i][1]
print(n - ans)
### BUGGY CODE ###

from collections import defaultdict
import sys
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    def __init__(self, n):
        '''
        n = 要素数
        要素の添字iは 0 <= i < n となる
        '''
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, value):
        '''i番目の要素にvalueを加算する O(logN)'''
        i = i + 1
        while i <= self.n:
            self.bit[i] += value
            i += i & -i

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def sum(self, l, r):
        '''区間[l, r)の和を求める O(logN)'''
        return self._sum(r) - self._sum(l)


input = sys.stdin.readline
N, Q = map(int, input().split())
C = list(map(int, input().split()))
LR = [tuple(map(int, input().split())) for _ in range(Q)]
query = [[] for _ in range(N)]
for i, (l, r) in enumerate(LR):
    query[l-1].append((i, r-1))

hist = defaultdict(lambda: -1)
nx = [-1] * N
for i in range(N-1, -1, -1):
    nx[i] = hist[C[i]]
    hist[C[i]] = i

bit = BIT(N)
ans = [None]*Q
for l in range(N-1,-1,-1):
    if nx[l] != -1:
        bit.add(nx[l],-1)
    for i,r in query[l]:
        ans[i] = (r-l+1) + bit.sum(l,r+1)

print(*ans,sep = '\n')

### FIXED CODE ###

from collections import defaultdict
import sys
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    def __init__(self, n):
        '''
        n = 要素数
        要素の添字iは 0 <= i < n となる
        '''
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, value):
        '''i番目の要素にvalueを加算する O(logN)'''
        i = i + 1
        while i <= self.n:
            self.bit[i] += value
            i += i & -i

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def sum(self, l, r):
        '''区間[l, r)の和を求める O(logN)'''
        return self._sum(r) - self._sum(l)


input = sys.stdin.readline
N, Q = map(int, input().split())
C = list(map(int, input().split()))
LR = [tuple(map(int, input().split())) for _ in range(Q)]
query = [[] for _ in range(N)]
for i, (l, r) in enumerate(LR):
    query[l-1].append((i, r-1))

hist = defaultdict(lambda: -1)
nx = [-1] * N
for i in range(N-1, -1, -1):
    nx[i] = hist[C[i]]
    hist[C[i]] = i

bit = BIT(N)
ans = [None]*Q
for l in range(N-1,-1,-1):
    if nx[l] != -1:
        bit.add(nx[l],-1)
    for i,r in query[l]:
        ans[i] = (r-l+1) + bit.sum(l,r+1)

print(*ans,sep = '\n')
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


k = int(input())
sum = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            sum += gcd(a,b,c)

print(sum)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


k = int(input())
sum = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        if gcd(a,b) == 1:
            sum += 1 * k
            continue
        for c in range(1,k+1):
            sum += gcd(a,b,c)

print(sum)
### BUGGY CODE ###

n = input()

monster = [int(x) for x in input().split()]

while(True):
	minIndex = monster.index(min(monster))
	for i in range(len(monster)): 
		if i == minIndex or monster[i] == 0:
			continue
		if monster[i] % monster[minIndex] == 0:
			monster[i] = 0
		else:
			monster[i] -= monster[minIndex] * (monster[i]//monster[minIndex])
	while(monster.count(0) > 0):
		monster.pop(monster.index(0))
	if len(monster) == 1:
		print(monster[0])
		break

### FIXED CODE ###

n = input()

monster = [int(x) for x in input().split()]

while(True):
	minIndex = monster.index(min(monster))
	for i in range(len(monster)): 
		if i == minIndex or monster[i] == 0:
			continue
		if monster[i] % monster[minIndex] == 0:
			monster[i] = 0
		else:
			monster[i] -= monster[minIndex] * (monster[i]//monster[minIndex])
	monster = [x for x in monster if x != 0]
	if len(monster) == 1:
		print(monster[0])
		break
### BUGGY CODE ###

# inputを高速化する。
import sys
input = sys.stdin.readline

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

dp = [0] * (W+1)

for i in range(N):
    w,v = map(int, input().split())
    for j in reversed(range(0,W+1)):
        if j + w <= W:
            dp[j+w] = max(dp[j+w], (dp[j]+v))
        

print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np

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

dp = np.zeros(W+1 , np.int64)


for i in range(N):
    w,v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:] , dp[:-w] + v)

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

# きりみんちゃんの配信をみてたので期待値は分かる
n, k = map(int, input().split())
arr = list(map(int, input().split()))
lis = [0 for _ in range(n)]
for i in range(n):
    lis[i] = sum(list(range(1, arr[i] + 1))) / arr[i]
ans = 0
for i in range(0, n - k + 1):
    ans = max(ans, sum(lis[i : i + k]))
print(ans)


### FIXED CODE ###

# きりみんちゃんの配信をみてたので期待値は分かる
# 素直にTLEくらったので累積和で加減する
# え これでもだめなの
# あほだった sumしてるし
# 単純にみたら 0.5ずつ増えてるのでそうするか
# 1WA...
# N = 1の場合か？


n, k = map(int, input().split())
arr = list(map(int, input().split()))
table = {}
ans = 0
for i in range(1, 1000 + 1):
    table[i] = (i + 1) * 0.5
if n == 1:
    print(table[arr[0]])
    exit()
lis = [0 for _ in range(n)]
lis[0] = table[arr[0]]
for i in range(n - 1):
    if i + 1 < k:
        lis[i + 1] = lis[i] + table[arr[i + 1]]
    else:
        lis[i + 1] = lis[i] + table[arr[i + 1]] - table[arr[i - k + 1]]
    ans = max(ans, lis[i + 1])
print(ans)
### BUGGY CODE ###

n = int(input())
s = [" "] + list(input())
q = int(input())
k = list(map(int, input().split()))



def find_ans(k:int):
    d__ = 0
    dm_ = 0
    _m_ = 0
    ans = 0
    
    for i in range(1, n+1):
        
        if s[i] == 'C':
            ans += dm_

        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                d__ -= 1
                dm_ -= _m_
                
            elif s[i-k+1] == 'M':
                _m_ -= 1
                
        if s[i] == 'D':
            d__ += 1    
        
        elif s[i] == 'M':
            dm_ += d__
            _m_ += 1

            
    return ans
        
for ki in k:
    print(find_ans(ki))

### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = " " + ns()
q = ni()
k = list(li())

def find_ans(k:int):
    cnt = [0,0,0]
    ans = 0
    
    for i in range(1, n+1):
        
        if s[i] == 'C':
            ans += cnt[2]

        if i-k+1 > 0:
            if s[i-k+1] == 'D':
                cnt[0] -= 1
                cnt[2] -= cnt[1]
                
            elif s[i-k+1] == 'M':
                cnt[1] -= 1
                
        if s[i] == 'D':
            cnt[0] += 1    
        
        elif s[i] == 'M':
            cnt[2] += cnt[0]
            cnt[1] += 1

            
    return ans
        
for ki in k:
    print(find_ans(ki))
### BUGGY CODE ###

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

s = [1]
while True:
  a = A[s[-1] - 1]
  if a in s:
    print(-1)
    break
  if a == 2:
    print(len(s))
    break
  s.append(a)


### FIXED CODE ###

import itertools

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

a = 1
for i, _ in enumerate(range(N), 1):
  a = A[a - 1]
  if a == 2:
    break
if a == 2:
  print(i)
else:
  print(-1)
### BUGGY CODE ###

#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N,K = LMIIS()
    R,S,P = LMIIS()
    T = input()
    A = ''
    ans = 0
    for i in range(K):
        if T[i] == 'r':
            A += 'p'
            ans += P
        elif T[i] == 's':
            A += 'r'
            ans += R
        else:
            A += 's'
            ans += S
    for i in range(K,N):
        if T[i] == 'r':
            if A[i-K] != 'p':
                A += 'p'
                ans += P
            else:
                A += '-'
        elif T[i] == 's':
            if A[i-K] != 'r':
                A += 'r'
                ans += R
            else:
                A += '-'
        else:
            if A[i-K] != 's':
                A += 's'
                ans += S
            else:
                A += '-'
    print(ans)




if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N,K = LMIIS()
    R,S,P = LMIIS()
    T = input()
    A = [False]*N
    ans = 0
    # hand = {
    #     'r':
    # }
    score = {
        'r':P,
        's':R,
        'p':S
    }
    for i in range(K):
        # print(T[i],score[T[i]])
        ans += score[T[i]]
        A[i] = True
    for i in range(K,N):
        if T[i] != T[i-K]:
            # print(T[i],score[T[i]])
            ans += score[T[i]]
            A[i] = True
        else:
            if A[i-K] != True:
                ans += score[T[i]]
                A[i] = True
            # print(T[i],0)
    print(ans)
    # for i in range(K):
    #     if T[i] == 'r':
    #         A += 'p'
    #         ans += P
    #     elif T[i] == 's':
    #         A += 'r'
    #         ans += R
    #     else:
    #         A += 's'
    #         ans += S
    # for i in range(K,N):
    #     if T[i] == 'r':
    #         if A[i-K] != 'p':
    #             A += 'p'
    #             ans += P
    #         else:
    #             A += '-'
    #     elif T[i] == 's':
    #         if A[i-K] != 'r':
    #             A += 'r'
    #             ans += R
    #         else:
    #             A += '-'
    #     else:
    #         if A[i-K] != 's':
    #             A += 's'
    #             ans += S
    #         else:
    #             A += '-'





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

from fractions import gcd
K = int(input())

ans =  0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans = ans + gcd(gcd(i,j),k)

print(ans)

### FIXED CODE ###

from math import gcd
K = int(input())

ans =  0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans = ans + gcd(gcd(i,j),k)

print(ans)