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

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

q = int(input())
v_to_qi = [[] for _ in range(n)]
v_to_l = [[] for _ in range(n)]
qv_list = []
for i in range(q):
    v, l = map(int, input().split())
    v -= 1
    qv_list.append(v)
    v_to_qi[v].append(i)
    v_to_l[v].append(l)

MAX = 10**5
# dp[i+1][j] = (i番目まで見て重さの合計がj以下のの時の価値の最大値)
dp = [[0] * (MAX + 1) for _ in range(20)]
ans = [0] * q

flag = [False] * n
for v in qv_list:
    flag[v] = True
    while v > 0:
        v //= 2
        flag[v] = True


def dfs(v, depth):
    for j in range(MAX + 1):
        if j < items[v][1]:
            dp[depth + 1][j] = dp[depth][j]
        else:
            dp[depth + 1][j] = max(dp[depth][j],
                                   dp[depth][j - items[v][1]] + items[v][0])

    if len(v_to_qi[v]) > 0:
        for qi, l in zip(v_to_qi[v], v_to_l[v]):
            ans[qi] = dp[depth + 1][l]

    if v * 2 + 1 < n and flag[v * 2 + 1]:
        dfs(v * 2 + 1, depth + 1)
    if v * 2 + 2 < n and flag[v * 2 + 2]:
        dfs(v * 2 + 2, depth + 1)


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


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


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

import sys


def get_array(): return list(map(int, sys.stdin.readline().strip().split()))


def get_ints(): return map(int, sys.stdin.readline().strip().split())


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


def maxim(i, char):
    if i < 0:
        return 0

    if li[i][char] != -1:
        ##print('hi')
        ##print(i,char)
        return li[i][char]
    if char == 2:
        li[i][2] = max(c[i] + maxim(i - 1, 1), c[i] + maxim(i - 1, 0))
        return li[i][2]
    if char == 1:
        li[i][1] = max(b[i] + maxim(i - 1, 0), b[i] + maxim(i - 1, 2))
        return li[i][1]
    if char == 0:
        li[i][0] = max(a[i] + maxim(i - 1, 1), a[i] + maxim(i - 1, 2))
        return li[i][0]
    if char == 3:
        li[i][3] = (max(maxim(i - 1, 2), maxim(i - 1, 1), maxim(i - 1, 0)))
        return li[i][3]


n = int(input())
a, b, c = [], [], []
for _ in range(n):
    x, y, z = get_ints()
    li = [[-1 for i in range(4)] for j in range(n+1)]
    a.append(x)
    b.append(y)
    c.append(z)
print(maxim(n , 3))

### FIXED CODE ###

import sys
def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


n=int(input())
a, b, c = [], [], []
for _ in range(n):
    x,y,z=get_ints()
    
    a.append(x)
    b.append(y)
    c.append(z)
li=[[-1 for i in range(3)]for j in range(n)]
li[0][0],li[0][1],li[0][2]=a[0],b[0],c[0]
for i in range(1,n):


        li[i][0] = max(a[i] + li[i-1][1] ,a[i] + li[i - 1][2])

        li[i][1] = max(b[i] + li[i - 1][0], b[i] +li[i - 1][2])

        li[i][2] = max(c[i] + li[i - 1][1], c[i] + li[i - 1][0])
print(max(li[n-1]))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
q = int(input())
b = []
c = []
for i in range(q):
    ans = 0
    x,y = map(int,input().split())
    for j in range(n):
        if a[j] == x:
            a[j] = y
        ans += a[j]
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
tmp = [0] * 100001
ans = 0
for i in range(n):
    tmp[a[i]] += 1
    ans += a[i]
q = int(input())
for i in range(q):
    x,y = map(int,input().split())
    ans -= x * tmp[x]
    ans += y * tmp[x]
    tmp[y] += tmp[x]
    tmp[x] = 0
    print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
dict={}
dict["R"]=[]
dict["G"]=[]
dict["B"]=[]
res=set()
for i in range(n):
  if s[i]=="R":
    dict["R"].append(i)
  elif s[i]=="G":
    dict["G"].append(i)
  elif s[i]=="B":
    dict["B"].append(i)
  else:
    raise Exception
for r in dict["R"]:
  for g in dict["G"]:
      for b in dict["B"]:
        if 2*r!=g+b and 2*g!=r+b and 2*b!=r+g:
            tup=frozenset([r,g,b])
            res.add(tup)             
print(len(res))

### FIXED CODE ###

n=int(input())
s=input()
dict={}
dict["R"]=[]
dict["G"]=[]
dict["B"]=[]
for i in range(n):
  if s[i]=="R":
    dict["R"].append(i)
  elif s[i]=="G":
    dict["G"].append(i)
  elif s[i]=="B":
    dict["B"].append(i)
  else:
    raise Exception
res=len(dict["R"])*len(dict["G"])*len(dict["B"])
for r in dict["R"]:
  for g in dict["G"]:
      if (r+g)%2==0:
        if s[(r+g)//2]=="B":
          res-=1
      try:
        if s[2*r-g]=="B" and 2*r-g>=0:
          	res-=1
      except:pass
      try:
        if s[2*g-r]=="B" and 2*g-r>=0:
          res-=1
      except:pass      
      
print(res)
### BUGGY CODE ###

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

d = {}

for item in s:
    if not item in d.keys():
        d[item] = 1
    else:
        d[item] += 1

m = [k for k, v in d.items() if v == max(d.values())]
m.sort()

for item in m:
    print(item)


### FIXED CODE ###

from collections import Counter
import itertools

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

cnt_words = Counter(s)

mode_v = cnt_words.most_common()[0][-1]
it = itertools.takewhile(
    lambda kv: kv[-1] == mode_v, cnt_words.most_common()
)
m = []
for i in it:
    m.append(i[0])
m.sort()
for item in m:
    print(item)
### BUGGY CODE ###

import sys
N,M=map(int,input().split())

graph=[]
for _ in range(N+1):
  graph.append([])

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  if t>300003:
    print(-1)
    sys.exit()
  
  nlist = []
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      table[v][t%3]=True
      for vv in graph[v]:
        if not table[vv][(t+1)%3]:
          nlist.append(vv)          
          #table[vv][t%3]=True
          #print((vv,t%3))
      
  #print((t,nlist))
  vlist = nlist
  


### FIXED CODE ###

import sys
N,M=map(int,input().split())

graph=[]
for _ in range(N+1):
  graph.append([])

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  #if t>300003:
  #  print(-1)
  #  sys.exit()
  
  #nlist = []
  nset = set()
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      table[v][t%3]=True
      for vv in graph[v]:
        if not table[vv][(t+1)%3]:
          #nlist.append(vv)
          nset.add(vv)
          #table[vv][t%3]=True
          #print((vv,t%3))
      
  #print((t,nlist))
  #vlist = nlist
  vlist = list(nset)
  if len(vlist) == 0:
    print(-1)
    break
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

def solve(ab, hp, memo):
  if hp <= 0:
    return 0
  else:
    ans = 10**10
    if not hp in memo:
      for attack, cost in ab:
        ans = min(ans, solve(ab, hp-attack, memo)+cost)
      memo[hp] = ans
    return memo[hp]

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
print(solve(AB, H, {}))

### FIXED CODE ###

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [10**10]*(H+1)
memo[0] = 0
i = 0
while i <= H:
  for a, b in AB:
    memo[i] = min(memo[i], b+memo[max(0, i-a)])
  i += 1
print(memo[H])
### BUGGY CODE ###

n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 1
li = list[0]
thh = int(li[0])
ahh = int(li[1])
while h < n:
     listh = list[h]
     listhh = list[h-1]
     th = int(listh[0])
     ah = int(listh[1])
     l = 1
     m = 1
     while l*th < thh:
        l += 1
     while m*ah < ahh:
        m += 1
     a = max(l,m)
     thh = th*a
     ahh = ah*a
     h += 1
print(thh+ahh)

### FIXED CODE ###

from decimal import Decimal
n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 0
th = 1.0
ah = 1.0

def f1(a,b):
     if a%b == 0:
          return a/b
     else:
          return a//b + 1

while h < n:
     listh = list[h]
     x = int(listh[0])
     y = int(listh[1])
     m = max(f1(th,x),f1(ah,y))
     th = Decimal(m*x)
     ah = Decimal(m*y)
     h += 1
print(int(th+ah))
### BUGGY CODE ###

import math

def eratosthenes(limit):
    A = [i for i in range(2, limit + 1)]
    B = []
    C = [False for _ in range(limit + 4)]
    while True:
        a = min(A)
        if a > math.sqrt(limit):
            break
        B.append(a)
        i = 0
        while len(A) > i:
            if A[i] % a == 0:
                A.pop(i)
                continue
            i += 1
    for a in A:
        B.append(a)
    for b in B:
        C[b] = True
    return C

def main():
    Q = int(input())
    lr = []
    mr = 0
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        lr.append((l, r))
        mr = max(mr, r)
    A = eratosthenes(mr)
    for l, r in lr:
        c = 0
        for i in range(l, r + 1, 2):
            if A[i] and A[(i + 1) // 2]:
                c += 1
        ans.append(c)
    for c in ans:
        print(c)


main()


### FIXED CODE ###

import math

def eratosthenes():
    limit = 100001
    A = [i for i in range(2, limit)]
    B = [False for _ in range(limit + 1)]
    C = [0 for i in range(limit + 1)]
    while True:
        a = min(A)
        if a > math.sqrt(limit):
            break
        B[a] = True
        i = 0
        while len(A) > i:
            if A[i] % a == 0:
                A.pop(i)
                continue
            i += 1
    for a in A:
        B[a] = True
    for i in range(3, limit + 1, 2):
        if B[i] and B[(i + 1) // 2]:
            C[i] += 1
    for i in range(3, limit + 1):
        C[i] += C[i - 1]
    return C


def main():
    Q = int(input())
    C = eratosthenes()
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans.append(C[r] - C[l - 1])
    for c in ans:
        print(c)


main()
### BUGGY CODE ###

import collections
n, m = map(int, input().split())
linked = collections.defaultdict(set)
for i in range(1, n + 1):
  linked[i].add(i)

for i in range(m):
  a, b = map(int, input().split())
  linked[a] |= linked[b]

  linked[b] = linked[a]
  for t in linked[b]:
    linked[t] = linked[a]

n_connected = 0
n_group = 0
for s in linked.values():
  if s:
    n_group += 1
    n_connected += len(s)
    s.clear()
print((n - n_connected) + (n_group - 1))


### FIXED CODE ###

import collections
n, m = map(int, input().split())
linked = collections.defaultdict(list)
i2group = dict()

gid = n + 1
def get_root(i):
  if i not in linked:
    return i
  j = get_root(linked[i])
  linked[i] = j
  return j

def get_groups():
  return [get_root(i) for i in range(1, n + 1)]

for i in range(m):
  a, b = map(int, input().split())
  ra, rb = get_root(a), get_root(b)
  if ra == rb: continue
  linked[ra] = gid
  linked[rb] = gid
  gid += 1

g = get_groups()
print(len(set(g)) - 1)
exit()

n_connected = 0
n_group = 0
for s in linked.values():
  s = s[0]
  if s:
    n_group += 1
    n_connected += len(s)
    s.clear()
print((n - n_connected) + (n_group - 1))
### BUGGY CODE ###

N=int(input())
R=[0]*N
K=(N//2)-1
S=K+1
L=list(map(int,input().split()))
for i in range(N):
  R[i]=[L[i],i]
R=sorted(R)
for i in range(N):
  if R.index([L[i],i])<S:
    print(R[S][0])
  else:
    print(R[K][0])

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
n=N//2
R=sorted(L)
for i in L:
  if i>R[n-1]:
    print(R[n-1])
  else:
    print(R[n])
### BUGGY CODE ###

import math
n=int(input())
for i in range(1,n+1):
  max = int(math.sqrt(i))
  result = 0
  for x in range(1,max+1):
    max = int(math.sqrt(i - x * x))
    for y in range(1,max+1):
      if i - x * x - y * y - x * y < 1:
        continue
      max = int(math.sqrt(i - x * x - y * y - x * y))
      for z in range(1,max+1):
        if x * x + y * y + z * z + x * y + y * z + x * z == i:
          result += 1
  print(result)

### FIXED CODE ###

nn=int(input())
nc = [0] * (nn + 1)
for x in range(1, 100):
  for y in range(1, 100):
    for z in range(1, 100):
      a = x * x + y * y + z * z + x * y + x * z + y * z
      if a > nn:
        break
      nc[a] += 1
for i in range(1, nn + 1):
  print(nc[i])
### BUGGY CODE ###

n,q=list(map(int,input().split()))
s=[[' ',0]]
s+=[[c,1]for c in input()]
s+=[[' ',0]]
for i in range(q):
	t,d=input().split()
	if d=='L':
		for j in range(1,n+1):
			if s[j][0]==t:
				x=s[j][1]
				s[j][1]=0
				s[j-1][1]+=x
	else:
		for j in range(1,n+1):
			if s[j][0]==t:
				x=s[j][1]
				s[j][1]=0
				s[j+1][1]+=x
print(sum([m[1] for m in s[1:-1]]))

### FIXED CODE ###

n,q=map(int,input().split())
s=" "+input()+" "
td=[input().split()for _ in[0]*q]
def test(x):
	for t,d in td:
		if s[x]==t:x+=1 if d=="R"else -1
	return x
def bs(b,g,t):
	while abs(b-g)>1:
		k=(b+g)//2
		if test(k)==t:g=k
		else:b=k
	return g
l=bs(n+1,0,0)
r=bs(0,n+1,n+1)
print(r-l-1)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(N):
    num=0
    for j in range(N-1):
        if i+1==A[j]:
            num+=1
    print(num)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
result=[0]*N
for a in A:
    result[a-1]+=1
print("\n".join(map(str,result)))
### BUGGY CODE ###


import numpy as np
def receive_round_setting():
    round_settings = input()
    N, K, Q = round_settings.split(' ')
    N, K, Q = int(N), int(K), int(Q)
    participants = np.full(N, K, dtype='i')
    round_settings = {'N':N, 'K':K, 'Q':Q,
                    'participants':participants}
    return round_settings

def answer_question(round_settings):
    for i in range(round_settings['Q']):
        answerer = int(input()) - 1
        round_settings['participants'] -= 1
        round_settings['participants'][answerer] += 1
    return round_settings
        
def announce_resutl(round_setting):

    [print('Yes') if participant > 0 else print('No')
    for participant in round_settings['participants']]

if __name__ == '__main__':
    round_settings = receive_round_setting()
    round_settings = answer_question(round_settings)
    announce_resutl(round_settings)


### FIXED CODE ###


import numpy as np
def receive_round_setting():
    round_settings = input()
    N, K, Q = round_settings.split(' ')
    N, K, Q = int(N), int(K), int(Q)
    participants = np.full(N, K, dtype='i')
    round_settings = {'N':N, 'K':K, 'Q':Q,
                    'participants':participants}
    return round_settings

def answer_question(round_settings):
    round_settings['participants'] -= 1*round_settings['Q']
    answerers = np.zeros(shape=round_settings['N'], dtype='i')
    for _ in range(round_settings['Q']):
        answerer = int(input()) - 1
        answerers[answerer] += 1
    round_settings['participants'] += answerers
    return round_settings
        
def announce_resutl(round_setting):

    [print('Yes') if participant > 0 else print('No')
    for participant in round_settings['participants']]

if __name__ == '__main__':
    round_settings = receive_round_setting()
    if round_settings['Q'] < round_settings['K']:
        announce_resutl(round_settings)
    else:
        round_settings = answer_question(round_settings)
        announce_resutl(round_settings)
    # round_settings = receive_round_setting()
    # round_settings = answer_question(round_settings)
    # announce_resutl(round_settings)
### BUGGY CODE ###

import math

n = int(input())
a = sorted(list(map(int, input().split())))
memo = ['Yes'] * n
ans = 0
max = a[-1]

for i, a_i in enumerate(a):
    if memo[i] == 'No':
        continue
    for j in range(i+1, n):
        if a[j] % a_i == 0:
            memo[j] = 'No'
    if i != n-1 and a_i == a[i+1]:
        continue
    ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
a = sorted(list(map(int, input().split())))
max = a[-1]
memo = ['Yes'] * (10**6+1)
ans = 0

for i, a_i in enumerate(a):
    if memo[a_i] == 'No':
        continue
    for j in range(a_i, max+1, a_i):
        memo[j] = 'No'
    if i != n-1 and a_i == a[i+1]:
        continue
    ans += 1

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

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

ans %= mod
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0
total = sum(a)
for i in range(n):
    total -= a[i]
    ans += a[i]*total
    ans %= mod
print(ans)
### BUGGY CODE ###

N = int(input())
A = tuple(map(lambda n: int(n) - 1, input().split()))

if not 0 in A:
    print(-1)
else:
    for j in range(N+1):
        # jは残す数
        if j in A:
            nf = A.index(j)
            A = A[nf:]
        else:
            break

    print(N - j)

### FIXED CODE ###

N = int(input())
A = tuple(map(lambda n: int(n) - 1, input().split()))

rem = 0
bk = 0
for a in A:
    if a == rem:
        rem += 1
    else:
        bk += 1

if bk == N:
    print(-1)
else:
    print(bk)
### BUGGY CODE ###

N = int(input())

A = list(map(int, input().split()))

for i in range(N):
  print(A.count(i+1))  


### FIXED CODE ###

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

B = [0] * N

for i in A:
  B[i-1] = int(B[i-1]) + 1
  
for j in B:
  print(j)
### BUGGY CODE ###

#ABC116D-VariousSushi.py

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = []
Score, Test = 0, 0
flag1, flag2 = 0, 0
kind = []
kindnumber = 0

for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters.append((INPUT2[0], INPUT2[1]))

Parameters = sorted(Parameters, key=lambda x: x[1], reverse=True)

def binanrySearch(kind, target):
    testkind = kind[:]
    testkind.sort()
    left, right = 0, len(testkind)-1
    while(right >= left):
        mid = int((right + left) / 2)
        if testkind[mid] == target:
            return True
        elif testkind[mid] > target:
            right = mid - 1
        elif testkind[mid] < target:
            left = mid + 1
    return False

def SumScore(List, K, kindnumber):
    taste = 0
    for i in range(K):
        taste += List[i][1]
    return taste + kindnumber * kindnumber

def SearchNew(List, K, kind):
    newkind = -1
    for i in range(len(List)-K):
        if binanrySearch(kind, List[K+i][0]) == False:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K, kind):
    result = -1
    for i in range(K):
        testkind = kind[:]
        testkind.pop(K-1-i)
        if binanrySearch(testkind, List[K-1-i][0]) == True:
            result = K-1-i
            break
    return result

for i in range(K):
    kind.append(Parameters[i][0])
kindnumber = len(set(kind))
Score = SumScore(Parameters, K, kindnumber)
kind.clear()

for t in Parameters:
    for i in range(K):
        kind.append(Parameters[i][0])
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, K, kind)
    j = SearchDouble(Parameters, K, kind)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    if i != -1 and j != -1:
        kindnumber += 1
    else:
        break
    Test = SumScore(Parameters, K, kindnumber)
    if Score <= Test:
        Score = Test
    kind.clear()

print(Score)


### FIXED CODE ###

#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

INPUT.sort(key = lambda x: -x[1])

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)
### BUGGY CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**8)

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = list(map(str, input().rstrip()))

cir = defaultdict(list)
for i in range(k):
    cir[i] = t[i::k]


def solve(li, r, s, p):
    v = []

    def f(li, v):
        if len(li) == 0:
            return 0

        score = 0

        # グーを出す時
        if "r" not in v:
            x = "r"
            if li[0] == "s":
                score = max(score, f(li[1:], ["r"]) + r)
            else:
                score = max(score, f(li[1:], ["r"]))

        # チョキを出す時
        if "s" not in v:
            x = "s"
            if li[0] == "p":
                score = max(score, f(li[1:], ["s"]) + s)
            else:
                score = max(score, f(li[1:], ["s"]))

        # パーを出す時
        if "p" not in v:
            x = "p"
            if li[0] == "r":
                score = max(score, f(li[1:], ["p"]) + p)
            else:
                score = max(score, f(li[1:], ["p"]))

        return score
    return f(li, v)


ans = []
for i in range(k):
    ans.append(solve(cir[i], r, s, p))

print(sum(ans))

### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = list(map(str, input().rstrip()))

cir = defaultdict(list)
for i in range(k):
    cir[i] = t[i::k]


def solve(sq):
    # 初手
    x = sq[0]
    if x == "r":
        before, score = "r", p
    elif x == "s":
        before, score = "s", r
    else:
        before, score = "p", s
    cnt = 1

    # 前回と違う手なら問答無用で勝てる、前回と同じ手なら奇数回目に勝てる
    for x in sq[1:]:
        if before != x:
            if x == "r":
                score += p
            elif x == "s":
                score += r
            else:
                score += s
            before = x
            cnt = 1
        elif cnt % 2 == 1:
            cnt += 1
        else:
            if x == "r":
                score += p
            elif x == "s":
                score += r
            else:
                score += s
            cnt += 1
    return score


ans = []
for i in range(k):
    ans.append(solve(cir[i]))

print(sum(ans))