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

import sys
input = sys.stdin.readline

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j in range(n):
            weight = cost[v][j]
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if r != (alt - 1) // l and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
q = int(input())

for i in range(q):
  s,t = map(int, input().split())
  ans = ans_list[s-1][t-1]
  if ans == float("inf"):
    ans = -1
  else:
    ans = (ans - 1) // l
  print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def dijkstra(s,n,cost,l):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        dist_v = d[v]
        for j, weight in enumerate(cost[v]):
            alt = dist_v + weight
            r = (dist_v - 1) // l
            if r != ((alt - 1) // l) and dist_v != 0:
                alt = (r + 1) * l + weight         
            d[j] = min(d[j],alt)
    return d

n,m,l = map(int, input().split())
path = [[float("inf") for i in range(n)] for i in range(n)]
ans_list = []
for i in range(m):
  a,b,cost = map(int, input().split())
  a -= 1
  b -= 1
  if cost <= l:
    path[a][b] = cost
    path[b][a] = cost
for s in range(n):
  ans_list.append(dijkstra(s,n,path,l))
q = int(input())

for i in range(q):
  s,t = map(int, input().split())
  ans = ans_list[s-1][t-1]
  if ans == float("inf"):
    ans = -1
  else:
    ans = (ans - 1) // l
  print(ans)
### BUGGY CODE ###

def create_anagram_dic(val):
  dic = {}
  for s in val:
    if s not in dic:
      dic[s] = 0
    dic[s] += 1
  
  return dic

def is_anagram(val, dic):
  for k, v in dic.items():
    if val.count(k) != v:
      return False
  return True

N = int(input())

s = list()
for i in range(0, N):
  val = str(input())
  s.append(val)
  
result_dic = {}
result_dic[s[0]] = 1

for i in range(1, len(s)):
  is_contain = False
  for k in result_dic.keys():
    dic = create_anagram_dic(k)
    if is_anagram(s[i], dic):
      result_dic[k] += 1
      is_contain = True
      break
  if not is_contain:
    result_dic[s[i]] = 1

result_count = 0
for val in result_dic.values():
  result_count += val * (val - 1) // 2

print(result_count)

### FIXED CODE ###

# 入力部
N = int(input())

s = list()
for i in range(0, N):
  val = str(input())
  s.append(val)
  
# 計算部
result_dic = {}

for i in range(0, len(s)):
  sorted_val = ''.join(sorted(s[i]))
  if sorted_val in result_dic:
    result_dic[sorted_val] += 1
  else:
    result_dic[sorted_val] = 1

result_count = 0
for val in result_dic.values():
  result_count += val * (val - 1) // 2

print(result_count)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    ans = 0
    for i, ai in enumerate(A):
        for j, aj in enumerate(A[i+1:]):
            ans += (ai * aj) % MOD
    
    print(ans % MOD)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    ans = 0

    B = [sum(A[1:])]
    for i, a in enumerate(A[1:-1]):
        B.append(B[i] - a)

    for i, ai in enumerate(A[:-1]):
        ans += (ai * B[i]) % MOD
    
    print(ans % MOD)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

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

def main(N,M,to_,from_):
    ans = "IMPOSSIBLE"
    
    for to in to_:
        if to in from_:
            ans = "POSSIBLE"
            break
            
    print(ans)

if __name__ == '__main__':
    N, M = map(int, input().split())
    to_, from_ = [], []
    for i in range(M):
        a, b = map(int, input().split())
        if(a==1):
            to_.append(b)
        elif(b==N):
            from_.append(a)
    main(N,M,to_,from_)

### FIXED CODE ###

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

def main(N,M,visited,queue):
    ans = "IMPOSSIBLE"

    for i in queue:
        if visited[i-1] == True:
            ans = "POSSIBLE"
            break
            
    print(ans)

if __name__ == '__main__':
    N, M = map(int, input().split())
    visited,queue = [False]*N, []
    for i in range(M):
        a, b = map(int, input().split())
        if(a==1):
            visited[b-1] = True
        elif(b==N):
            queue.append(a)
    main(N,M,visited,queue)
### BUGGY CODE ###

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

def main():
    N,D,A = map(int,readline().split())
    m = map(int,read().split())
    X,H = map(list,zip(*sorted(zip(m,m))))
    count = 0
    for i in range(N):
        if H[i] > 0:
            bomb = (H[i]+A-1)//A
            count += bomb
            damage = bomb * A
            for j in range(i,N):
                if X[j] <= X[i] + 2*D:
                    H[j] -= damage
                else:
                    break

    print(count)

if __name__ == "__main__":
    main()


### FIXED CODE ###

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

def main():
    N,D,A = map(int,readline().split())
    m = map(int,read().split())
    X,H = zip(*sorted(zip(m,m)))
    
    over = [-1]*N
    tmp=0
    for i in range(N):
      while(tmp<N and X[i]+D*2>=X[tmp]):
        tmp += 1
      over[i] = tmp
    reset = [0]*N
    
    ans = 0
    dam = 0
    for i in range(N):
      if i>0:
        reset[i] += reset[i-1]
      hp = H[i]-dam+reset[i]
      if hp > 0:
        bomb = (hp+A-1)//A
        ans += bomb
        dam += bomb * A
        if(over[i]<N):
          reset[over[i]] += bomb * A

    print(ans)

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

N,C = map(int, input().split())
L = [[int(a) for a in input().split()] for _ in range(N)]

ans = [[0, 0] for _ in range(C)]
L.sort()
for i in range(N):
    j = 0
    while j < C:
        if ans[j][0] == L[i][0] and ans[j][1] == L[i][2]:
            ans[j][0] = L[i][1]
            j = C
        elif ans[j][0] < L[i][0]:
            ans[j][0] = L[i][1]
            ans[j][1] = L[i][2]
            j = C
        j += 1
    ans.sort(reverse=True)
    
num = 0
for i in range(C):
    if ans[i][0] > 0:
        num += 1
        
print(num)

### FIXED CODE ###

N,C = map(int, input().split())
L = [[int(a) for a in input().split()] for _ in range(N)]

ans = [0]*C
chan = [0]*C
L.sort()
for i in range(N):
    for j in range(C):
        if ans[j] == L[i][0] and chan[j] == L[i][2]:
            ans[j] = L[i][1]
            break
        elif ans[j] < L[i][0]:
            ans[j] = L[i][1]
            chan[j] = L[i][2]
            break
    ans.sort(reverse=True)
    
num = 0
for i in range(C):
    if ans[i] > 0:
        num += 1
        
print(num)
### BUGGY CODE ###

n, m = map(int, input().split())
city = []
for i in range(m):
    city.append(list(map(int, input().split())))

sortedcity = sorted(city)
cnt = {}
ans = []

for i in range(m):
    pref = sortedcity[i][0]
    year = sortedcity[i][1]
    if pref in cnt:
        cnt[pref].append(year)
    else:
        cnt[pref] = [year]

for i in range(m):
    pref = city[i][0]
    year = city[i][1]
    num = cnt[pref].index(year) + 1
    tmp = str(pref).zfill(6) + str(num).zfill(6)
    ans.append(tmp)
    print(ans[i])


### FIXED CODE ###

n, m = map(int, input().split())
city = []
for i in range(m):
    x, y = map(int, input().split())
    city.append(list([x, y, i]))

city.sort()
cnt = 1

tmppref = city[0][0]

for i in range(m):
    city[i][1] = cnt
    cnt += 1
    if i < m - 1 and tmppref != city[i + 1][0]:
        cnt = 1
        tmppref = city[i+1][0]
city = sorted(city, key=lambda x: x[2])
for i in range(m):
    pref = city[i][0]
    num = city[i][1]
    ans = str(pref).zfill(6) + str(num).zfill(6)
    print(ans)
### BUGGY CODE ###

import numpy as np
import re
prog = re.compile('AC')
N, Q = [int(x) for x in input().split()]
S = input()
result = prog.finditer(S)
pos = np.array([res.start()+1 for res in result])

for _ in range(Q):
  l, r = [int(x) for x in input().split()]
  print(np.count_nonzero(np.logical_and(pos>=l, pos<=r-1)))

### FIXED CODE ###

import numpy as np
def find_AC(S):
  ret = [0]*len(S)
  for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
      ret[i+1] = 1
  return ret

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

cum = np.cumsum(find_AC(S))

for _ in range(Q):
  l, r = [int(x) for x in input().split()]
  ans = cum[r-1] - cum[l-1]
  print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
a = []
for _ in range(H):
    a.append(input())
queue = deque([])
dist = [[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            queue.append([i,j])
            dist[i][j] = 0
dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]
while len(queue) != 0:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        elif dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w] +1
            queue.append([nh, nw])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dist[i][j])
print(ans)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
a = []
for _ in range(H):
    a.append(input())
queue = deque([])
dist = [[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            queue.append([i,j])
            dist[i][j] = 0
dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]
while len(queue) != 0:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        elif dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w] +1
            queue.append([nh, nw])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dist[i][j])
print(ans)
### BUGGY CODE ###

import numpy as np
import collections

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

for k in range(1, n+1):
    counts = collections.Counter(a).values()
    counts = sorted(list(counts), reverse=True)
    
    eat = 0
    while True:
        if np.count_nonzero(counts) < k:
            break
        else:
            for i in range(k):
                counts[i] -= 1
            eat += 1
            counts = sorted(list(counts), reverse=True)
            
    print(eat)
            

### FIXED CODE ###

import collections
import numpy as np

# リストarrからx個の同じ長さの列を取り出す時の最大の長さ
# 発想: x個取り出す時、ある文字をx個より多く取り出して列に含むことはない
#       一方ある文字をその文字がある数よりも取り出して使うこともできない
#       つまり、min(arr.count(a), x)で、x個の同じ長さの列に使えるaの数がわかる
#       さらに、sum(min(arr.count(a),x))で、x個の同じ長さの列に使える文字の数がわかる
#       よって、sum(min(arr.count(a),x))//xで、x個の同じ長さの列の長さがわかる
#       発展的に、longest(arr,x)までの計算状況からlongest(arr,x+1)が計算できる
# def longest(arr, x):    # legacy
#     return sum(min(arr.count(a), x) for a in arr) // x


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

counter = collections.Counter(a)        #O(n)
nums = list(counter.values())           #O(n)
num_counter = collections.Counter(nums) #O(n)
lastest_add = np.count_nonzero(nums)    #O(n)
building, longests = [0], [0]
for i in range(1, n+1):                 #O(n)
    appended = building[-1] + lastest_add   #O(1)
    building.append(appended)               #O(1)
    longests.append(appended // i)          #O(1)
    lastest_add -= num_counter[i]           #O(1)


lastest_longest = 0
k_most = []
for i, x in enumerate(reversed(longests)):
    while x > lastest_longest:
        lastest_longest += 1
        k_most.append(n-i)

k_most.extend([0]*(n-len(k_most)))      # zero padding

for longests_num in k_most:
    print(longests_num)

# print('----------------')
# for k in range(1, n+1):
#     maxindexes = list(i for i, x in enumerate(longests) if x >= k)
#     if maxindexes:
#         print(maxindexes[-1])
#     else:
#         print(0)
### BUGGY CODE ###

import sys
# import collections
# import math
# import string
# import bisect
# import re
# import itertools
# import statistics

def primeNums(n):
    from math import floor, sqrt
    sieve = set(range(2, n + 1))
    if 2 in sieve:
        not_prime = set(range(2 * 2, n + 1, 2))
        sieve -= not_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            not_prime = set(range(i * 2, n + 1, i))
            sieve -= not_prime
    return sieve

limit = 10 ** 5
prime_table = [0 for _ in range(limit + 1)]
for p in primeNums(limit):
    prime_table[p] = 1

def main():

    q = int(sys.stdin.readline().rstrip())
    m = map(int, sys.stdin.read().split())

    for l, r in zip(m, m):
        res = 0
        for i in range(l if l % 2 == 1 else l + 1, r + 1, 2):
            res += (prime_table[(i + 1) // 2] if prime_table[i] else 0)
        
        print(res)


if __name__ == "__main__":
    # execute only if run as a script
    main()


### FIXED CODE ###

import sys
# import collections
# import math
# import bisect
# import re
# import itertools


def primeNums(n):
    from math import floor, sqrt
    sieve = set(range(2, n + 1))
    if 2 in sieve:
        not_prime = set(range(2 * 2, n + 1, 2))
        sieve -= not_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            not_prime = set(range(i * 2, n + 1, i))
            sieve -= not_prime
    return sieve

limit = 10 ** 5
prime_table = [0 for _ in range(limit + 1)]
for p in primeNums(limit):
    prime_table[p] = 1

like_2017_table = [0 for _ in range(limit + 1)]
for i in range(3, limit + 1, 2):
    if prime_table[i] and prime_table[(i + 1) // 2]:
            like_2017_table[i] = 1

s = [0 for _ in range(limit + 1)]
for i in range(limit):
    s[i+1] = s[i] + like_2017_table[i+1]

def main():

    q = int(sys.stdin.readline().rstrip())
    m = map(int, sys.stdin.read().split())

    for l, r in zip(m, m):
        res = s[r] - s[l-1]
        print(res)


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

#
# abc077 c
#
import sys
from io import StringIO
import unittest
import bisect


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2
1 5
2 4
3 6"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
1 1 1
2 2 2
3 3 3"""
        output = """27"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """6
3 14 159 2 6 53
58 9 79 323 84 6
2643 383 2 79 50 288"""
        output = """87"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    A.sort()
    B.sort()
    C.sort()

    ans = 0
    for a in A:
        bi = bisect.bisect(B, a)
        BT = B[bi:]
        for b in BT:
            ans += len(C) - bisect.bisect(C, b)

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

#
# abc077 c
#
import sys
from io import StringIO
import unittest
import bisect


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2
1 5
2 4
3 6"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
1 1 1
2 2 2
3 3 3"""
        output = """27"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """6
3 14 159 2 6 53
58 9 79 323 84 6
2643 383 2 79 50 288"""
        output = """87"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    A.sort()
    B.sort()
    C.sort()

    ans = 0
    for b in B:
        an = bisect.bisect_left(A, b)
        cn = N - bisect.bisect_right(C, b)
        ans += an*cn

    print(ans)


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

N = int(input())
A = list(map(int,input().split()))
j = 0
for i in range(1,len(A)+1) :
    ans = A.count(i)
    print(ans)
    A = [n for n in A if n != i]
    if len(A) == 0 :
        j = i
        break
for i in range(N-j) :
    print('0')

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
C = [0] * N
for i in range(len(A)) :
    x = A[i]
    C[x-1] += 1
for i in range(N) :
    print(C[i])
### BUGGY CODE ###

n = int(input())
su = 0
for i in range(1,n+1):
  a = i
  l = (n//i)*i
  m = (n//i)/2
  su += m*(a+l)
print(int(su))

### FIXED CODE ###

n = int(input())
su = 0
for i in range(1,n+1):
  t = n//i
  l = t*i
  m = t/2
  su += m*(i+l)
print(int(su))
### BUGGY CODE ###

N = int(input())
X = input()
X_arr = list(X)
N, X = int(N), int(X, 2)
MAX_N = 2 * 10 ** 5


def popcount(x):
    cnt = 0
    for i in range(x.bit_length()):
        if x & 1 << i:
            cnt += 1
    return cnt


memo = [0] * (MAX_N + 1)
for i, n in enumerate(range(1, MAX_N + 1), start=1):
    cnt = 0
    while n:
        p = popcount(n)
        n = n % p
        cnt += 1
    memo[i] = cnt


x_popcount = popcount(X)
p_upper, p_downer = x_popcount + 1, x_popcount - 1
y_upper = X % p_upper
y_downer = X % p_downer if p_downer else None

for i in range(N):
    if X_arr[i] == '0':
        z = (y_upper + pow(2, (N - i - 1)) % p_upper) % p_upper
    else:
        if not p_downer:
            print(0)
            continue
        z = (y_downer - pow(2, (N - i - 1)) % p_downer) % p_downer

    print(memo[z] + 1)


### FIXED CODE ###

N = int(input())
X = input()
X_arr = list(X)
N, X = int(N), int(X, 2)
MAX_N = 2 * 10 ** 5


def popcount(x):
    cnt = 0
    for i in range(x.bit_length()):
        if x & 1 << i:
            cnt += 1
    return cnt


memo = [0] * (MAX_N + 1)
for i, n in enumerate(range(1, MAX_N + 1), start=1):
    cnt = 0
    while n:
        p = popcount(n)
        n = n % p
        cnt += 1
    memo[i] = cnt


x_popcount = popcount(X)
p_upper, p_downer = x_popcount + 1, x_popcount - 1
y_upper = X % p_upper
y_downer = X % p_downer if p_downer else None

for i in range(N):
    if X_arr[i] == '0':
        z = (y_upper + pow(2, (N - i - 1), p_upper)) % p_upper
    else:
        if not p_downer:
            print(0)
            continue
        z = (y_downer - pow(2, (N - i - 1), p_downer)) % p_downer

    print(memo[z] + 1)
### BUGGY CODE ###

a, b, x = map(int, input().split())
ans = 0
for i in range(a, b+1):
    if i % x == 0:
        ans +=1
print(ans)

### FIXED CODE ###

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

if a % x == 0:
    print(-(a//x)+(b//x)+1)
else:
    print(-(a//x)+(b//x))
### BUGGY CODE ###

INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i + arr[j]] = max(dp[i + arr[j]], dp[i] + 1)
ans = ''
while(N>0):
    for i in src[::-1]:
        if N - arr[i] > 0 and dp[N-arr[i]] == dp[N] - 1:
            ans += str(i)
            N -= arr[i]
            break
print(ans if ans else 0)

### FIXED CODE ###

INF = 10**10
arr = [INF,2,5,5,4,5,6,3,7,6]
N,M = map(int,input().split())
src = sorted(list(map(int,input().split())))

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for j in src:
        if i + arr[j] <= N:
            dp[i+arr[j]] = max(dp[i+arr[j]],dp[i] + 1)
dim = dp[N]
ans  = ''
while(dim > 0):
    for i in src[::-1]:
        if N >= arr[i] and dp[N-arr[i]] + 1 == dp[N]:
            ans += str(i)
            N -= arr[i]
            dim -= 1
            break
print(ans)
### BUGGY CODE ###

N,K =map(int,input().split())
R,S,P = map(int,input().split())
T =input()
ans = 0
for i in range(len(T)):
    if i < K:
        if T[i] == "r":
            ans += P
        elif T[i] == "s":
            ans += R
        else:
            ans += S
    else:
        if T[i] == T[i-K]:
            T = T[:i] + "R" + T[i+1:]
        if T[i] == "r":
            ans += P
        elif T[i] == "s":
            ans += R
        elif T[i] == "p":
            ans += S
print(ans)

### FIXED CODE ###

N,K =map(int,input().split())
R,S,P = map(int,input().split())
T =input()
ans = 0
chk_list = [0] * len(T)
for i in range(len(T)):
    if i < K:
        if T[i] == "r":
            ans += P
        elif T[i] == "s":
            ans += R
        else:
            ans += S
    else:
        if T[i] == T[i-K]:
            if chk_list[i-K] == 0:
                chk_list[i] =1
                continue
        if T[i] == "r":
            ans += P
        elif T[i] == "s":
            ans += R
        elif T[i] == "p":
            ans += S
print(ans)