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

def lcs(X, Y):
    X = " " + X
    Y = " " + Y
    #c = [[0 for j in xrange(len(Y))] for i in xrange(len(X))]
    c = [[0] * len(Y) for i in xrange(len(X))]
    maxl = 0
    
    for i in xrange(1,len(X)):
        for j in xrange(1,len(Y)):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
            maxl = max(maxl, c[i][j])
    return maxl
n = int(raw_input())
 
for i in xrange(n):
    s1 = raw_input()
    s2 = raw_input()
    print lcs(s1, s2)

### FIXED CODE ###

def lcs(X, Y):
    #X = " " + X
    #Y = " " + Y
    #c = [[0 for j in xrange(len(Y))] for i in xrange(len(X))]
    c2 = [0 for i in xrange(len(Y) + 1)]
    #maxl = 0
     
    for i in xrange(len(X)):
        c1 = c2 + []
        for j in xrange(len(Y)):
            if X[i] == Y[j]:
                c2[j + 1] = c1[j] + 1
            elif c2[j + 1] < c2[j]:
                c2[j + 1] = c2[j]
    return c2[-1]
n = int(raw_input())
  
for i in xrange(n):
    s1 = raw_input()
    s2 = raw_input()
    print lcs(s1, s2)
### BUGGY CODE ###

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
RL = []
for i in range(q):
  l, r = map(int, input().split())
  RL.append((r, l, i))
RL.sort()
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for r, l, i in RL:
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

### FIXED CODE ###

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted(r*U+i for i, (l, r) in enumerate(LR))
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for w in W:
  r, i = divmod(w, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")
### BUGGY CODE ###

#!/usr/bin/env python3
import math

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        sa = input().split(' ')
        l.append(int(sa[0]))
        r.append(int(sa[1]))

    r_max = 100000
    primes = [True for i in range(r_max)]
    primes[0] = False
    primes[1] = False
    i = 2
    max_i = int(math.sqrt(r_max))
    while i <= max_i:
        for j in range(i * 2, r_max, i):
            primes[j] = False
        while i <= max_i:
            i += 1
            if primes[i]:
                break

    for i in range(Q):
        c = 0
        for j in range(l[i], r[i] + 1, 2):
            if primes[j] and primes[int((j + 1) / 2)]:
                c += 1
        print(c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import math

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        na = list(map(int, input().split()))
        l.append(na[0])
        r.append(na[1])

    r_max = 100000
    primes = [True for i in range(r_max)]
    like_numbers = [0 for i in range(r_max)]

    primes[0] = primes[1] = False
    max_i = int(math.sqrt(r_max))
    i = 2
    while i <= max_i:
        primes[i] = True
        for j in range(i * i, r_max, i):
            primes[j] = False
        while i <= max_i:
            i += 1
            if primes[i]:
                break

    for i in range(3, r_max, 2):
        if primes[i] and primes[int((i + 1) / 2)]:
            like_numbers[i] = 1

    c = 0
    for i in range(3, r_max, 2):
        if like_numbers[i]:
            c += 1
        like_numbers[i] = c


    for i in range(Q):
        if l[i] == 1:
            print(like_numbers[r[i]])
        else:
            print(like_numbers[r[i]] - like_numbers[l[i] - 2])

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

X = int(input())

for i in range(-200000, 200000):
    if (i+3)**5 - (i+2)**5 == X:
        # print(i, (i+3)**5 , (i+2)**5)
        print((i+3), (i+2))
        break
    elif (i+3)**5 + (i+2)**5 == X:
        # print(i, (i+3)**5 , (i+2)**5)
        print((i+3), -(i+2))
        break
    elif -(i+3)**5 - (i+2)**5 == X:
        # print(i, (i+3)**5 , (i+2)**5)
        print(-(i+3), (i+2))
        break
    elif -(i+3)**5 + (i+2)**5 == X:
        # print(i, (i+3)**5 , (i+2)**5)
        print(-(i+3), -(i+2))
        break

### FIXED CODE ###

X = int(input())

for a in range(-200, 200):
    for b in range(-200, 200):
        if a**5-b**5 == X:
            print(a, b)
            break
    else:
        continue
    break
### BUGGY CODE ###

from math import factorial

#inputは文字列として取得
input1=input()
input2=input()
#splitする必要がある
input2=input2.split(" ")

N=int(input1)
D=[int(s) for s in input2]

ans=None

if D.count(0)==1 and D[0]==0:

    mul=1
    n=1

    for i in range(1,max(D)+1):
        m=D.count(i)
        mul*=n**m
        n=m
    
    ans=mul%998244353

else:
    ans=0

print(int(ans))

### FIXED CODE ###

#inputは文字列として取得
input1=input()
input2=input()
#splitする必要がある
input2=input2.split(" ")

N=int(input1)
D=[int(s) for s in input2]

ans=None


if D.count(0)==1 and D[0]==0:

    L=[0]*(max(D)+1)

    for i in range(len(D)):
        L[D[i]]+=1

    mul=1

    for i in range(len(L)-1):
        mul*=L[i]**L[i+1]%998244353
    
    ans=mul%998244353

else:
    ans=0

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

def permutation_modp(n,k):
    ans=1
    for i in range(k):
        ans*=(n-i)
    return ans
num_vertax,num_coler=map(int,input().split())
ver_array=[0]*num_vertax
for i in range(num_vertax-1):
    a,b=map(int,input().split())
    ver_array[a-1]+=1
    ver_array[b-1]+=1
ans=num_coler
ans*=permutation_modp(num_coler-1,ver_array.pop(0))
for ver in ver_array:
    ans*=permutation_modp(num_coler-2,ver-1)
print(ans%1000000007)

### FIXED CODE ###

N,K=map(int,input().split())
mod=1000000007
path=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  path[a].append(b)
  path[b].append(a)
#print(path)
  
abc=[False for i in range(N)] #0ならまだ塗ってない
 
abc[0]=True
cnt=0
ans=K%mod
nx=[]
for i in range(len(path[0])):
  child=path[0][i]
  if abc[child]:
    continue
  ans=ans*(K-1-cnt)
  ans=ans%mod
  cnt=cnt+1
  abc[child]=True
  nx.append(child)
while len(nx)>0:
  a=nx.pop()
  cnt=0
  for i in range(len(path[a])):
    child=path[a][i]
    if abc[child]:
      continue
    ans=ans*(K-2-cnt)
    ans=ans%mod
    cnt=cnt+1
    abc[child]=True
    nx.append(child)
      
print(ans%mod)
### BUGGY CODE ###

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

for i in range(1, n + 1):
    cnt = 0
    for j in a:
        if i == j:
            cnt += 1
        else:
            pass
    print(cnt)

### FIXED CODE ###

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

res = [0] * n
for i in range(len(a)):
    res[a[i]-1] += 1

[print(j) for j in res]
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

a = sorted(a)
max_a = a[-1]
left_med_a = a[n//2-1]
right_med_a = a[n//2]

if cmb(max_a, left_med_a) < cmb(max_a, right_med_a):
    print(max_a, right_med_a)
else:
    print(max_a, left_med_a)

### FIXED CODE ###

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

a = sorted(a)
max_a = a[-1]
max_a_harf = (max_a+1) // 2

ans = 0
for i in range(n):
    if abs(max_a_harf - a[i]) < abs(max_a_harf - ans):
        ans = a[i]

print(max_a, ans)
### BUGGY CODE ###

n = int(input())

ans = 0

for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        ans += j

print(ans)


### FIXED CODE ###

n = int(input())

ans = n * (n + 1) // 2

is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, n + 1):
    ans += i
    for j in range(2, n // i + 1):
        is_prime[i * j] = False
        ans += i * j

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

H, W, M = [int(n) for n in input().split()]
H_freq = [0] * H
W_freq = [0] * W

coordinates = {}
for m in range(M):
    h, w = [int(n)-1 for n in input().split()]
    H_freq[h] += 1
    W_freq[w] += 1
    if h in coordinates.keys():
        coordinates[h].append(w)
    else:
        coordinates[h] = [w]

max_h = max(H_freq)
max_w = max(W_freq)
most_freqent_h = [i for i, h in enumerate(H_freq) if h == max_h]
most_freqent_w = [i for i, w in enumerate(W_freq) if w == max_w]

ans = 0
for h in most_freqent_h:
    for w in most_freqent_w:
        if w in coordinates[h]:
            ans = max_h + max_w - 1
        else:
            ans = max_h + max_w
            print(ans)
            exit()
print(ans)


### FIXED CODE ###

H, W, M = [int(n) for n in input().split()]
H_freq = [0] * H
W_freq = [0] * W

table = []
for m in range(M):
    h, w = [int(n)-1 for n in input().split()]
    H_freq[h] += 1
    W_freq[w] += 1
    table.append((h, w))

max_h = max(H_freq)
max_w = max(W_freq)
most_freqent_h = [i for i, h in enumerate(H_freq) if h == max_h]
most_freqent_w = [i for i, w in enumerate(W_freq) if w == max_w]

count = 0
for (h, w) in table:
    if H_freq[h] == max_h and W_freq[w] == max_w:
        count += 1

if count < len(most_freqent_h) * len(most_freqent_w):
    print(max_h + max_w)
else:
    print(max_h + max_w - 1)
### BUGGY CODE ###

N = int(input())

count = 0

for i in range(N-1):
  for j in range(N-1):
    if (i+1)*(j+1) < N:
      count += 1
    else:
      break
print(count)

### FIXED CODE ###

N = int(input())

count = 0

for i in range(N-1):
  count = count + int((N-1)/(i+1))
  
print(count)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
def ans(a,x):
  b=0
  c=a[:x]+a[x+1:]
  d=list(set(c))
  for i in range(len(d)):
    if c.count(d[i])>1:
      b=b+(c.count(d[i])*(c.count(d[i])-1))/2
  return b
for k in range(n):
  print(int(ans(a,k)))


### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
s=Counter(a)
res=0
for i in s.values():
    res+=i*(i-1)//2
ans=0
for j in range(n):
    if s[a[j]]==1:
        print(res)
    else:
        ans=res-s[a[j]]+1
        print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]
 
 
def f(h, w):
    c = 0
    for hh in range(h, -1, -1):
        if S[hh][w] == '#':
            break
        c += 1
    for hh in range(h, H):
        if S[hh][w] == '#':
            break
        c += 1
    for ww in range(w, -1, -1):
        if S[h][ww] == '#':
            break
        c += 1
    for ww in range(w, W):
        if S[h][ww] == '#':
            break
        c += 1
    return c - 3
 
 
def main():
    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            ans = max(ans, f(h, w))
    print(ans)
 
 
main()

### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]


def main():
    cnt = [[0] * W for _ in range(H)]
    for h in range(H):
        done = [0] * W
        for w in range(W):
            if S[h][w] == '#' or done[w] == 1:
                continue
            c = 0
            while W > w + c:
                if S[h][w + c] == '#':
                    break
                c += 1
            for k in range(c):
                cnt[h][w + k] += c
                done[w + k] = 1
    for w in range(W):
        done = [0] * H
        for h in range(H):
            if S[h][w] == '#' or done[h] == 1:
                continue
            c = 0
            while H > h + c:
                if S[h + c][w] == '#':
                    break
                c += 1
            for k in range(c):
                cnt[h + k][w] += c
                done[h + k] = 1
    ans = 0
    for r in cnt:
        for c in r:
            ans = max(ans, c - 1)
    print(ans)


main()
### BUGGY CODE ###

def main():
    V = int(input())
    flag = True
    ans = 0

    G = [[int(i) for i in input().split()] for i in range(V)]
    for i in range(V):
        G[i][i] = float("inf")
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if G[i][k] + G[k][j] < G[i][j] < float("inf"):
                    flag = False
                    break
                elif G[i][j] == G[i][k] + G[k][j]:
                    G[i][j] = float("inf")

    for i in range(V):
        for j in range(i, V):
            if G[i][j] < float("inf"):
                ans += G[i][j]

    if flag:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def solve(V, G):
    ans = 0
    for i in range(V - 1):
        for j in range(i + 1, V):
            direct = G[i][j]
            for k in range(V):
                if k == i or k == j:
                    continue
                ind = G[i][k] + G[k][j]
                if direct > ind:
                    return -1
                elif direct == ind:
                    break
            else:
                ans += direct
    return ans


def main():
    V = int(input())
    G = [[int(i) for i in input().split()] for i in range(V)]
    print(solve(V, G))


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

from sys import stdin

def main():

    n = int(stdin.readline().strip())
    a = list(map(int, stdin.readline().strip().split()))

    if n == 1:
        print(1)
        exit()

    a.sort()

    # bにチェックする数を追加していく
    b = []
    ans = 0

    for i in range(n):

        if a[i] == a[i-1]:
            continue

        flag = True
        for j in b:
            if a[i] % j == 0:
                flag = False
                break

        if flag:
            b.append(a[i])
            if i == n-1 or a[i] != a[i+1]:
                ans += 1

    print(ans)

main()


### FIXED CODE ###

from sys import stdin

def main():

    n = int(stdin.readline().strip())
    a = list(map(int, stdin.readline().strip().split()))

    if n == 1:
        print(1)
        exit()

    a.sort()

    dp = [True] * (a[-1] + 1)
    ans = 0

    for i in range(n):

        if a[i] == a[i-1]:
            continue

        if dp[a[i]]:

            for j in range(2 * a[i], a[-1] + 1, a[i]):
                dp[j] = False

            if i == n-1 or a[i] != a[i+1]:
                ans += 1

    print(ans)

main()
### BUGGY CODE ###

import math


x,y = map(int,input().split())

flag=False
if (x+y)%3 == 0:
    k = (x+y)//3
    if abs(x-y) <=k :
        l = abs(x-y)
        if (k-l)%2==0:
            flag=True
            a = (k+l)//2
            b = (k-l)//2
            c = math.factorial(k)//(math.factorial(a)*math.factorial(b))

if flag:
    print(int(c%(10**9+7)))
else:
    print(0)

### FIXED CODE ###

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

x,y = map(int,input().split())

flag=False
if (x+y)%3 == 0:
    k = (x+y)//3
    if abs(x-y) <=k :
        l = abs(x-y)
        if (k-l)%2==0:
            flag=True
            a = (k+l)//2
            #b = (k-l)//2
            c = comb(k,a ,10**9+7)

if flag:
    print(c)
else:
    print(0)
### BUGGY CODE ###

k, s  = map(int, input().split())

ans1 = 0
ans2 = 0
ans3 = 0

for i in range(k+1):
    for j in range(i, k+1):
        for l in range(j, k+1):
            if i + j + l == s:
                if i == j == l:
                    ans1 +=1
                elif i == l or i == j or j == l:
                    ans2 += 1
                else:
                    ans3 += 1
                    

print(ans1+ans2*3+ans3*6)


### FIXED CODE ###

k, s  = map(int, input().split())

ans1 = 0
ans2 = 0
ans3 = 0

for i in range(k+1):
    for j in range(i, k+1):    
        if 0 <= s-i-j <= k and j <= s-i-j:
            if i == j == s-i-j:
                ans1 +=1
            elif i == s-i-j or i == j or j == s-i-j:
                ans2 += 1
            else:
                ans3 += 1
                    

print(ans1+ans2*3+ans3*6)
#print(ans1, ans2, ans3)
### BUGGY CODE ###

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    # b = list(map(int, input().split()))
    b = [int(i) for i in input().split()] 
  else:
    # b = [1,2,1]
    # b = [2,2]
    b = [1,1,1,2,2,1,2,3,2]
    N = len(b)
    
  if check(b) != True:
    print(-1)
    
def check(B):
  # if 'get_ipython' in globals(): print(B)
  lenB = len(B)
  if lenB == 0 :
    return True
  else :
    maxB = max(B)
    if maxB > lenB: maxB = lenB
  # for i in reversed(range(lenB)):
  for i in reversed(range(0,maxB)):
    if B[i] == i+1:
      if check(B[:i]+B[(i+1):]) == True:
        print(B[i])
        return True
        break
    
main()

### FIXED CODE ###

import sys

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    b = [int(i) for i in input().split()] 
  else:
    # b = [1,2,1]
    # b = [2,2]
    b = [1,1,1,2,2,1,2,3,2]
    N = len(b)

  ans = []
  while True:
    for i in range(N-1,-1,-1):
      if b[i] == i+1:
        ans.append(i+1)
        del b[i]
        N = N -1
        break
      if i == 0:
        print(-1)
        sys.exit()
    if N == 0:
      break

  for i in reversed(ans):
    print(i)
    
main()
### BUGGY CODE ###

def rec(depth, w, v):
    if w > maxW:
        return
    WV[depth][w] = max(v, WV[depth][w])
    if depth+1 >= N:
        return
    rec(depth+1, w+W[depth+1], v+V[depth+1])
    rec(depth+1, w, v)


N, maxW = map(int, input().split())
WV = [[-1 for i in range(maxW+1)] for j in range(N)]
W = [0 for i in range(N)]
V = [0 for i in range(N)]
for i in range(N):
    W[i], V[i] = map(int, input().split())
rec(0, 0, 0)
rec(0, W[0], V[0])
print(max(WV[-1]))


### FIXED CODE ###

N, maxW = map(int, input().split())
WV = [[0 for i in range(maxW+1)] for j in range(N+1)]
W = [0 for i in range(N+1)]
V = [0 for i in range(N+1)]
for i in range(1, N+1):
    W[i], V[i] = map(int, input().split())

for i in range(1, N+1):
    for w in range(maxW+1):
        WV[i][w] = max(WV[i-1][w], WV[i][w])
        nw = w + W[i]
        if nw <= maxW:
            WV[i][nw] = WV[i-1][w] + V[i]

print(max(WV[-1]))
### BUGGY CODE ###

s = input()
a = "".join([chr(97 + i) for i in range(26)])
b = "".join([a[i - 1] for i in range(26)])
x = str.maketrans(a, b)
while True:
    s = s.translate(x)
    if " the " in s or "that " in s or "this " in s:
        print(s)
        break


### FIXED CODE ###

import sys
a = "abcdefghijklmnopqrstuvwxyz"
x = str.maketrans(a, a[1:] + a[:1])
for s in sys.stdin:
    while True:
        s = s.translate(x)
        if "the" in s or "that" in s or "this " in s:
            print(s, end = "")
            break
### BUGGY CODE ###

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

total=0

def check(a,b,c):
    if(a<b+c):
        if(b<a+c):
            if(c<a+b):
                return True
    return False

for i in range(len(D)):
    for j in range(i+1,len(D)):
        for k in range(j + 1, len(D)):
            if(check(D[i],D[j],D[k])):
                total+=1

print(total)


### FIXED CODE ###

import bisect

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

D.sort()
total=0

for i in range(N-2):
    for j in range(i+1,N-1):
        total+=bisect.bisect_left(D,D[i]+D[j])-j-1

print(total)
### BUGGY CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(1000):
    str_i = str(i).zfill(3)
    i_ptr = 0
    s_ptr = 0
    
    while True:
        if i_ptr >= len(str_i):
            cnt += 1
            break

        while s_ptr <= len(s) - 1 and s[s_ptr] != str_i[i_ptr]:
            s_ptr += 1
        if s_ptr >= len(s):
            break
        i_ptr += 1
        s_ptr += 1
print(cnt)

### FIXED CODE ###

from string import digits

n = int(input())
s = input()

cnt = 0
for i in digits:
    x = s.find(i)
    if x == -1:
        continue
    for j in digits:
        y = s.find(j, x + 1)
        if y == -1:
            continue
        for k in digits:
            z = s.find(k, y + 1)
            if z == -1:
                continue
            cnt += 1

print(cnt)
### BUGGY CODE ###

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

A_set = list(set(A))

A_count =[]
for i in range(len(A_set)):
    A_count.append(A.count(A_set[i]))

A_count.sort()

ans=0
for i in range(len(A_set)-K):
    ans += A_count[i]

print(ans)


### FIXED CODE ###

from collections import Counter
N, K=list(map(int, input().split()))
A=list(map(int, input().split()))

X=Counter(A)
X2 = sorted(X.items(), key=lambda x:x[1])
ans=0
for i in range(len(X2)-K):
    ans+=X2[i][1]
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()
#T r→P点
#T s→R点
#T p→S点
r=0;s=1;p=2;m=3
#dp[r,s,p][range(N)]:
#dp[i][j]:j番目まで見たとき、最後がiのときのmax
def calc(U):
    M=len(U)
    dp=[[0 for j in range(M+1)] for i in range(4)]
    j=0
    if U[j]=="r":
        dp[p][j+1]=dp[m][j]+P
    elif U[j]=="s":
        dp[r][j+1]=dp[m][j]+R
    else:
        dp[s][j+1]=dp[m][j]+S
    dp[m][j+1]=max(dp[r][j+1],dp[s][j+1],dp[p][j+1])
    for j in range(1,M):
        for i in range(3):
            dp[i][j+1]=max(dp[(i+1)%3][j],dp[(i+2)%3][j])
        #print(dp[0][j+1],dp[1][j+1],dp[2][j+1])
        if U[j]=="r":
            dp[p][j+1]+=P
        elif U[j]=="s":
            dp[r][j+1]+=R
        else:
            dp[s][j+1]+=S
        dp[m][j+1]=max(dp[r][j+1],dp[s][j+1],dp[p][j+1])
    #for line in dp:
    #    print(line)
    
    return dp[3][-1]
Y=["" for i in range(K)]
for i in range(N):
    Y[i%K]=Y[i%K]+T[i]
#print(Y)
ans=0
for t in Y:
    k=calc(t)
    #print(t,k)
    ans+=k
print(ans)


### FIXED CODE ###

N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()
#T r→P点
#T s→R点
#T p→S点
r=0;s=1;p=2;m=3
#dp[r,s,p][range(N)]:
#dp[i][j]:j番目まで見たとき、最後がiのときのKおきの和のmax
dp=[[0 for j in range(N)] for i in range(4)]
for j in range(K):
    if T[j]=="r":
        dp[p][j]=P
    elif T[j]=="s":
        dp[r][j]=R
    else:
        dp[s][j]=S
    dp[m][j]=max(dp[r][j],dp[s][j],dp[p][j])
for j in range(K,N):
    for i in range(3):
        dp[i][j]=max(dp[(i+1)%3][j-K],dp[(i+2)%3][j-K])
    if T[j]=="r":
        dp[p][j]+=P
    elif T[j]=="s":
        dp[r][j]+=R
    else:
        dp[s][j]+=S
    dp[m][j]=max(dp[r][j],dp[s][j],dp[p][j])
ans=0
for i in range(K):
    ans+=dp[m][-i-1]
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
lim = 10**18
ans = 1
for a in A:
    ans *= a
if (ans > lim):
    print("-1")
else:
    print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
lim = 10**18
if A[-1] == 0:
    print("0")
    exit(0)
ans = 1
for a in A:
    ans *= a
    if (ans > lim):
        print("-1")
        exit(0)
print(ans)
### BUGGY CODE ###

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

l = list()
la = list()
ln = list()
for i in range(m):
    a, b = map(int, input().split())
    l.append([a, b])
    if 1 in [a, b]:
        la.append(a*b)
    if n in [a, b]:
        if a == n:
            ln.append(b)
        else:
            ln.append(a)

for i in ln:
    if i in la:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

### FIXED CODE ###

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

l = list()
la = [0] * (n+1)
ln = [0] * (n+1)

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        la[b] = 1
    elif b == 1:
        la[a] = 1
    if a == n:
        ln[b] = 1
    elif b == n:
        ln[a] = 1

for i in range(n+1):
    if la[i]*ln[i] == 1:
        print("POSSIBLE") 
        exit()

print("IMPOSSIBLE")