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


class Node(object):
  def __init__(self,name):
    self.name=name
    self.value = 0
    self.nodes_names = []
    self.nodes = []
  
  def set_nodes(self,all_Nodes_dic):
    for name,node in all_Nodes_dic.items():
      if name in self.nodes_names:
        self.nodes.append(node)
  
  def update_value(self,val):
    self.value += val
    for node in self.nodes:
      node.update_value(val)



def main():
  N,Q = map(int,input().split())
  all_Nodes = {}
  tasks=[]
  for _ in range(N-1):
    name,pname = map(int,input().split())
    if name not in all_Nodes.keys():
      node = Node(name)
      node.nodes_names.append(pname)
      all_Nodes.update({name:node})
    else:
      node = all_Nodes[name]
      node.nodes_names.append(pname)
    
    if pname not in all_Nodes.keys():
      node = Node(pname)
      all_Nodes.update({pname:node})
  
  for _ in range(Q):
    node_name,point = map(int,input().split())
    tasks.append((node_name,point))

  for node in all_Nodes.values():
    node.set_nodes(all_Nodes)
  
  for name,value in tasks:
    parent = all_Nodes[name]
    parent.update_value(value)
  
  sorted_lst = sorted(list(all_Nodes.values()), key=lambda x:x.name)

  print(" ".join([str(node.value) for node in sorted_lst]))
  return


if __name__ == "__main__":
  main()





### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())

trees = [ [] for i in range(n+1) ]
for i in range(n-1):
    a, b = map(int, input().split())
    trees[a].append(b)
    trees[b].append(a)

values = [ 0 for i in range(n+1) ]
for i in range(q):
    p, x = map(int, input().split())
    values[p] += x
#print(values)

def dfs2(i, parent):
    for j in trees[i]:
        if j == parent: continue
        values[j] += values[i]
        dfs2(j, i)

dfs2(1, -1)
print(*values[1:])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    a,e=map(int,input().split())
    graph[a-1].append(e+n-1)
    graph[a+n-1].append(e+2*n-1)
    graph[a+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
visited=[False]*(3*n)

def dfs(checking,length=0):
    visited[checking]=True
    ret=3*n
    for next in graph[checking]:
        if t==next:
            ret=length+1
            break
        if visited[next]:
            continue
        ret=min(ret,dfs(next,length+1))
    visited[checking]=False
    return ret

ans = dfs(s,0)//3
if ans >= n:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))

N, M = inpl()
uv = [ set() for _ in range(3*N) ]
vu = [ set() for _ in range(3*N) ]
for _ in range(M):
    u, v = inpl()
    for k in range(3):
        uv[u-1 + k*N].add(v-1 + ((k+1)%3)*N)
        vu[v-1 + ((k+1)%3)*N].add(u-1 + k*N)
S, T = inpl()
S -= 1
T -= 1

cur = set({S})
for i in range(3*N):
    if i % 3 == 0 and T in cur:
        print(i//3)
        break
    elif len(cur) == 0:
        print(-1)
        break
    prev = cur
    cur = set()
    for u in prev:
        for fr in vu[u]:
            uv[fr].remove(u)
        cur |= uv[u]
else:
    print(-1)
### BUGGY CODE ###

n,m,s=map(int,input().split())
s=min(s,2500)
import networkx as nx
G = nx.DiGraph()
G.add_nodes_from(range(125000))
for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2501):
        G.add_edge(u-1+j*n,v-1+(j-a)*n,weight=b)
        G.add_edge(v-1+j*n,u-1+(j-a)*n,weight=b)
for i in range(n):
    c,d=map(int,input().split())
    c=min(c,2500)
    for j in range(2501-c):
        G.add_edge(i+j*n,i+(j+c)*n,weight=d)
    for j in range(2500):
        G.add_edge(i+(j+1)*n,i+j*n,weight=0)
d=nx.single_source_dijkstra_path_length(G, s*n)
for i in range(1,n):
    print(d[i])

### FIXED CODE ###

n,m,s=map(int,input().split())
s=min(s,2500)
edge=[[] for i in range(n*50*51)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2501):
        edge[u-1+j*n].append((v-1+(j-a)*n,b))
        edge[v-1+j*n].append((u-1+(j-a)*n,b))
for i in range(n):
    c,d=map(int,input().split())
    for j in range(2501-c):
        edge[i+j*n].append((i+(j+c)*n,d))
    for j in range(2500):
        edge[i+(j+1)*n].append((i+j*n,0))
from heapq import heappush,heappop,heapify
d = [float('inf') for i in range(n*50*51)]
pq = []
heappush(pq,(0,s*n))
while pq:
    weight,u = heappop(pq)
    if d[u]>weight:
        d[u]=weight
        for v,weight in edge[u]:
            heappush(pq,(d[u]+weight,v))
for i in range(1,n):
    print(d[i])
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)


def C(x):
    train = 0
    for a, f in zip(A, F):
        train += max(0, a - x // f)

    return train <= K


left = -1
right = 10 ** 12 + 1
while right > left + 1:
    mid = (right + left) // 2
    if C(mid):  # 食べきれる場合
        right = mid
    else:
        left = mid

ans = right
print(ans)


### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
F = np.array(input().split(), dtype=np.int64)
A = np.sort(A)
F = np.sort(F)[::-1]


def C(x):
    train = np.maximum(0, A - x // F).sum()
    return train <= K


left = -1
right = 10 ** 12 + 1
while right > left + 1:
    mid = (right + left) // 2
    if C(mid):  # 食べきれる場合
        right = mid
    else:
        left = mid

ans = right
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
    b.append(a[i])
    b = b[::-1]
for i in range(n - 1):
    print(b[i], end = " ")
print(b[n - 1], end = "")
print()


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
if n % 2 == 0:
    key = n - 1
else:
    key = n - 2
for i in range(key, 0, -2):
    b.append(a[i])
for i in range(0, n, 2):
    b.append(a[i])
if n % 2 != 0:
    b = b[::-1]
for i in range(n - 1):
    print(b[i], end = " ")
print(b[n - 1], end = "")
print()
### BUGGY CODE ###

from sys import stdin
from itertools import accumulate

def solve():
    file_input = stdin
     
    N = int(file_input.readline())
    img = tuple(tuple(map(int, line.split())) for line in file_input)
    
    acc_row = tuple(tuple(accumulate(line)) + (0,) for line in img)
    acc_col = tuple(tuple(accumulate(line)) + (0,) for line in zip(*img))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_i, acc_row_i = tpl_1
        for j, tpl_2 in enumerate(zip(img[i:], acc_row[i:]), start=i):
            img_j, acc_row_j = tpl_2
            
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
                
            if i == j:
                continue
            
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
            
            for acc_col_k, img_i_k, img_j_k in zip(acc_col[1:], img_i[1:], img_j[1:]):
                col = acc_col_k[j] - acc_col_k[i - 1]
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + img_i_k + img_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()


### FIXED CODE ###

from sys import stdin
from itertools import accumulate

def solve():
    file_input = stdin
    
    N = int(file_input.readline())
    G = tuple(tuple(map(int, line.split())) for line in file_input)
    G1 = tuple(t[1:] for t in G)
    
    # accumulated rows
    ar = ((0,) + tuple(accumulate(line)) for line in G)
    
    # accumulated columns
    ac = ((0,) + tuple(accumulate(line)) for line in zip(*G))
    ac_1 = next(ac)
    ac = tuple(zip(*ac))
    
    ans = 0
    for i, t1 in enumerate(zip(G1, ar, ac, ac_1)):
        G_i, ar_i, ac_i, ac_1i = t1
        ar_ii = ar_i[i]
        for j, t2 in enumerate(zip(G1[i:], ar_i[i+1:], ac[i+1:], ac_1[i+1:]), start=i):
            G_j, ar_ij, ac_j, ac_1j = t2
            single_row = ar_ij - ar_ii
            if single_row > ans:
                ans = single_row
                
            if i == j:
                continue
            
            col_max = ac_1j - ac_1i
            
            for ac_jk, ac_ik, G_ik, G_jk in zip(ac_j, ac_i, G_i, G_j):
                col = ac_jk - ac_ik
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + G_ik + G_jk
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def lcs(x, y):
    dp = {(0, 0): 0}
    for i in range(1, len(x) + 1):
        dp[(i, 0)] = 0
    for j in range(1, len(y) + 1):
        dp[(0, j)] = 0
    for i in range(1, len(x) + 1):
        for j in range(1, len(y) + 1):
            if x[i - 1] == y[j - 1]:
                dp[(i, j)] = dp[(i - 1, j - 1)] + 1
            else:
                dp[(i, j)] = max(dp[(i - 1, j)], dp[(i, j - 1)])

    return dp[(len(x), len(y))]


def lcs_sol(x, y):
    n = len(x)
    m = len(y)
    dp = [[0 for j in range(m + 1)] for i in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]

if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print(lcs_sol(x, y))



### FIXED CODE ###

def m():
 e=input
 a=''
 for _ in[0]*int(e()):
  X,z=e(),[]
  for y in e():
   s=i=0
   for k in z:
    t=X.find(y,s)+1
    if t<1:break
    if t<k:z[i]=t
    s=k;i+=1
   else:
    t=X.find(y,s)+1
    if t:z+=[t]
  a+=f'\n{len(z)}'
 print(a[1:])
if'__main__'==__name__:m()
### BUGGY CODE ###

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

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

wk = 1
li_answer = list()
for idx, v in enumerate(li_a):
    prev = wk
    if idx <= (k - 1):
        wk = wk * v
    else:
        wk = wk * v // li_a[idx - k]
        if prev >= wk:
            print('No')
        else:
            print('Yes')




### FIXED CODE ###

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

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

for idx, v in enumerate(li_a):
    if idx <= (k - 1):
        pass
    else:
        if v > li_a[idx - k]:
            print('Yes')
        else:
            print('No')
### BUGGY CODE ###

N,K=map(int,input().split())
ans=0
if N<K:
  pass
else:
  A=list(map(int,input().split()))
  for i in range(N-K):
    ans+=min(A)
    A.remove(min(A))  
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
ans=0
if N<=K:
  pass
else:
  A=list(map(int,input().split()))
  A.sort()
  ans=sum(A[:N-K])
print(ans)
### BUGGY CODE ###

def f(s, n, m):
    w_count = s.count('W')
    r_count = s.count('R')
    m = min(w_count, r_count)

    if s.find('WR') == -1:
        return n
    elif n > m:
        return m
    else:
        i, j = 0, -1
        while True:
            if s[j] == 'R':
                break
            else:
                j -= 1

        while True:
            if s[i] == 'W':
                break
            else:
                i += 1

        s = list(s)
        s[i] = 'R'
        s[j] = 'W'
        s = ''.join(s)

        return f(s, n+1, m)

N = int(input())
s = input()
print(f(s, 0, 0))

### FIXED CODE ###

from collections import Counter
N = int(input())
s = input()
c = Counter(s)
w, r = 0, c['R']
ans = max(w, r)
for i in range(N):
    if s[i] == 'W': w += 1
    else: r -= 1 
    ans = min(ans, max(w, r))

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

A,B,C,K=map(int,input().split())
if A==B==C:
  print('0')
  exit()
  
else:
  a=A
  b=B
  c=C
  for n in range(K):
    aa=b+c
    bb=c+a
    cc=a+b
    a=aa
    b=bb
    c=cc

if a-b>10**18:
  print('Unfair')
else:
  print(a-b)

### FIXED CODE ###

A,B,C,K=map(int,input().split())
if A==B==C:
  print('0')
  exit()
  
else:
  if K%2==0:
    key=A-B
    if key>10**18:
      print('Unfair')
    else:
      print(key)
  else:
    key=B-A
    if key>10**18:
      print('Unfair')
    else:
      print(key)
### BUGGY CODE ###

def main():

    S = input()
    Q = int(input())

    reverse = False
    for _ in range(Q):
        query= input()
        if query[0] == '1':
            reverse = not reverse
        elif query[2] == '1':
            if reverse:
                S = ''.join([S,query[4]])
            else:
                S = ''.join([query[4],S])
        elif query[2] == '2':
            if reverse:
                S = ''.join([query[4],S])
            else:
                S = ''.join([S,query[4]])

    if reverse:
        S = S[::-1]

    print(S)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():

    S = input()
    Q = int(input())

    reverse = False
    head = ''
    tail = ''

    for _ in range(Q):
        query= input()
        if query == '1':
            reverse = not reverse
            head, tail = tail, head
        else:
            _, f, c = query.split()
            if f == '1':
                head = ''.join([head,c])
            else:
                tail = ''.join([tail,c])

    if reverse:
        S = S[::-1]

    print(''.join([head[::-1], S, tail]))

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

D, G=list(map(int, input().split()))
#L[i][0]:i番目の問題数、L[i][0]:i番目のボーナス得点 調整のため[0]追加
L=[0]+[list(map(int, input().split())) for i in range(D)]
#f:i番目まで考えるときの最小問題数  
def f(G, i):
    l=[]
    if i==0:
        return 10000 
    for j in range(min(G//(i*100), L[i][0])+1):
        if j==L[i][0] and G-j*i*100-L[i][1]>0:
            l.append(f(G-j*i*100-L[i][1],i-1)+j)
        elif j==L[i][0] and G-j*i*100-L[i][1]<=0:
            l.append(L[i][0])
        elif G-j*i*100>0:
            l.append(f(G-j*i*100,i-1)+j)
        elif G-j*i*100<=0:
            l.append(j)
        else:break
    return min(l)

print(f(G,D))

### FIXED CODE ###

D, G=list(map(int, input().split()))
#L[i][0]:i番目の問題数、L[i][0]:i番目のボーナス得点
L=[0]+[list(map(int, input().split())) for i in range(D)]
 
#f:i番目まで考えるときの最小問題数  
def f(G, i):
    if i==0:
	    return 10000
    #n:i番目を絶対に解くときの問題数  
    n=min(G//(i*100), L[i][0])
    #s:i番目を絶対に解くときのスコア  
    s=n*i*100
    #全部解くとき、ボーナスもスコアに加える
    if n==L[i][0]:
        s+=L[i][1]
	#スコアに届かない時、届かない分はG-s点をi-1番目までで埋める
    if s<G:
        n+=f(G-s, i-1)
    #i-1番目までの方が少ない時はそっちを返す
    return min(n, f(G,i-1))
print(f(G, D))
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    P = LI()

    s = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            s[i][j] = min(i,N-1-i,j,N-1-j)

    r = [[1] * N for _ in range(N)]

    ans = 0
    for p in P:
        x = (p-1)//N
        y = (p-1) % N
        ans += s[x][y]
        r[x][y] = 0
        q = collections.deque()
        q.append((x,y,s[x][y]))
        while q:
            a,b,c = q.pop()
            nc = c + r[a][b]
            for da,db in ((1,0),(0,1),(-1,0),(0,-1)):
                na = a + da; nb = b + db
                if 0 < na < N-1 and 0 < nb < N-1:
                    if s[na][nb] <= nc: continue
                    s[na][nb] = nc
                    q.append((na,nb,nc))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    P = LI()

    s = []
    for i in range(N):
        for j in range(N):
            s.append(min(i,N-1-i,j,N-1-j))

    r = [1] * (N*N)

    ans = 0
    q = []
    for p in P:
        p -= 1
        ans += s[p]
        r[p] = 0
        q.append(p)
        while q:
            a = q.pop()
            nc = s[a] + r[a]

            if a >= N:
                if s[a-N] > nc:
                    s[a-N] = nc
                    q.append(a-N)
            if a + N < N*N:
                if s[a+N] > nc:
                    s[a+N] = nc
                    q.append(a+N)
            if a % N:
                if s[a-1] > nc:
                    s[a-1] = nc
                    q.append(a-1)
            if a % N < N -1:
                if s[a+1] > nc:
                    s[a+1] = nc
                    q.append(a+1)

    print(ans)

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

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

    res = []
    xorSum = 0

    for i in range(0,N-1):
        xorSum ^= A[i]
    
    res.append(xorSum)

    for i in range(N-1):
        xorSum = xorSum ^ A[::-1][i] ^ A[::-1][i+1]
        res.append(xorSum)
    
    print(" ".join(map(str, res[::-1])))

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    res = []
    xorSum = 0

    for i in range(0,N-1):
        xorSum ^= A[i]
    
    res.append(xorSum)
    A_reversed = A[::-1]

    for i in range(N-1):
        xorSum = xorSum ^ A_reversed[i] ^ A_reversed[i+1]
        res.append(xorSum)
    
    print(" ".join(map(str, res[::-1])))

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

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

    s = input().rstrip()
    t = input().rstrip()

    n = len(s)
    m = len(t)

    dp = [['' for _ in range(m + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        s_ = s[i - 1]
        for j in range(1, m + 1):
            t_ = t[j - 1]
            if s_ != t_:
                if len(dp[i - 1][j]) >= len(dp[i][j - 1]):
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i][j - 1]
            else:
                dp[i][j] = list(dp[i - 1][j - 1])
                dp[i][j].append(s_)
                dp[i][j] = "".join(dp[i][j])

    print(dp[-1][-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    s = input().rstrip()
    t = input().rstrip()

    n = len(s)
    m = len(t)

    dp = []
    for _ in range(n + 1):
        dp.append([0] * (m + 1))

    for i in range(1, n + 1):
        s_ = s[i - 1]
        for j in range(1, m + 1):
            t_ = t[j - 1]
            if s_ != t_:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            else:
                dp[i][j] = dp[i - 1][j - 1] + 1
    ans = []
    while n > 0 and m > 0:
        if dp[n][m] == dp[n][m - 1]:
            m -= 1
        elif dp[n][m] == dp[n - 1][m]:
            n -= 1
        else:
            ans.append(s[n - 1])
            n -= 1
            m -= 1
    print("".join(ans[::-1]))


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

n,a,b=map(int,input().split())
s=input()
ok=0
x=0
ans=""
for i in range(n):
    if s[i]=="a" and ok<a+b:
        ok+=1
        ans+="Yes\n"
    elif s[i]=="b" and ok<a+b and x<b:
        ok+=1
        x+=1
        ans+="Yes\n"
    else:
        ans+="No\n"

print(ans[:-1])


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,a,b=map(int,input().split())
s=input()
ok=0
x=0
ans=[]
for i in range(n):
    ss=s[i]
    if ss=="a" and ok<a+b:
        ok+=1
        ans.append("Yes")
    elif ss=="b" and ok<a+b and x<b:
        ok+=1
        x+=1
        ans.append("Yes")
    else:
        ans.append("No")

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

n,k=map(int,input().split())
mod=998244353
S=[]
for _ in range(k):
  l,r=map(int,input().split())
  S.append([l,r])
dp=[0 for _ in range(n+1)]
for i in range(k):
  for j in range(S[i][0],S[i][1]+1):
    dp[j]+=1

for i in range(1,n+1):
  for j in range(k):
    for l in range(S[j][0],S[j][1]+1):
      if i-l<1:
        continue
      dp[i]+=dp[i-l]
print(dp[n-1]%mod)

### FIXED CODE ###

n,k=map(int,input().split())
mod=998244353
R=[]
for _ in range(k):
  l,r=map(int,input().split())
  R.append([l,r])

dp=[0 for _ in range(n+1)]
dp[1]=1
dpsum=[0 for _ in range(n+1)]
dpsum[1]=1
for i in range(2,n+1):
  for j in range(k):
    li=i-R[j][1]
    ri=i-R[j][0]
    if ri<0:
      continue
    li=max(li,1)
    dp[i]+=(dpsum[ri]-dpsum[li-1])%mod
  dpsum[i]=dpsum[i-1]+dp[i]
  dpsum[i]%=mod
print(dp[n]%mod)
### BUGGY CODE ###

def main():
    s = input()
    t = input()
    sletters = set()
    for i in s:
        sletters.add(i)

    for i in t:
        if i not in sletters:
            print(-1)
            return

    i = 0
    j = 0
    ans = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            j += 1
        i += 1
        ans += 1
        if i == len(s):
            i = 0

    print(ans)


main()


### FIXED CODE ###

import bisect

def main():
    s = input()
    t = input()
    sletters = [0]*26
    for i in range(len(s)):
        x = ord(s[i])-ord('a')
        if sletters[x] == 0:
            sletters[x] = [i]
        else:
            sletters[x].append(i)

    ans = 0
    curr_index = -1
    for i in t:
        x = ord(i)-ord('a')
        if sletters[x] == 0:
            print(-1)
            return
        index = bisect.bisect(sletters[x],curr_index)
        #print(sletters[x],i,curr_index,index)
        if index == len(sletters[x]):
            ans += len(s)-curr_index
            curr_index = sletters[x][0]
            ans += curr_index
        else:
            ans += sletters[x][index]-curr_index
            curr_index = sletters[x][index]
        

    print(ans)


main()
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
sort_A = sorted(A)
sort_F = sorted(F,reverse=True)

def check(x):
    cnt = 0
    for i in range(N):
        tmp = x // sort_F[i]
        cnt += max(0, sort_A[i] - tmp)
    return cnt <= K



def main():
    ok = 10 ** 22
    ng = -1

    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid

    print(ok) 

if __name__ == "__main__":
    main()

### FIXED CODE ###

def isOK(mid,N,K,sort_F,sort_A):
    cnt = 0
    for i in range(N):
        cnt += max(sort_A[i] - (mid // sort_F[i]),0)
    return cnt <= K

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    sort_A = sorted(A)
    sort_F = sorted(F, reverse=True)

    ng = -1
    ok = 10 ** 12 + 5
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if isOK(mid,N,K,sort_F,sort_A):
            ok = mid
        else:
            ng = mid

    print(ok)



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

import itertools

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

ans = float('inf')
roots = list(itertools.permutations(a))

for i in range(n):
    sum_d = 0
    root = list(roots[i])
    for j in range(1, n):
        sum_d += min(abs(root[j] - root[j - 1]), abs(k - root[j] + root[j - 1]))
    if sum_d < ans:
        ans = sum_d
print(ans)


### FIXED CODE ###

k, n = map(int, input().split())
a = list(map(int, input().split()))
d_list = [] * n
for i in range(1, n):
    d_list.append(a[i] - a[i - 1])
d_list.append(k - a[n - 1] + a[0])
ans = sum(d_list) - max(d_list)
print(ans)