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

import sys


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

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

    L_MAX = 10**5
    D_TH = 11
    V_MAX = 1 << D_TH
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]

    for i, (val, w) in enumerate(items[:V_MAX]):
        for j in range(L_MAX + 1):
            i1 = i + 1
            i0 = (i + 1) // 2
            if j < w:
                dp[i1][j] = dp[i0][j]
            else:
                dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

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

        if v + 1 <= V_MAX:
            ans = dp[v + 1][l]
        else:
            items_sub = [items[v]]
            while v > V_MAX:
                v = (v - 1) // 2
                items_sub.append(items[v])

            ans = 0
            for bit in range(1 << len(items_sub)):
                s_val = s_w = 0
                for i, (val, w) in enumerate(items_sub):
                    if (bit >> i) & 1:
                        s_val += val
                        s_w += w
                if s_w <= l:
                    ans = max(ans, dp[V_MAX][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


### 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 ###

n = int(input())
a = list(map(int, input().split()))
s = 0
t = sum(a)
m = 10 ** 9 + 7
for i in range(n - 1):
    s += a[i] * (t - sum(a[0:i + 1])) % m
print(s % m)

### FIXED CODE ###

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

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

if 0.5 * M < N:
    print(1)

else:
    for i in range(N, M//2+1):
        if M % i == 0:
            print(M // i)
            exit()

    print(1)


### FIXED CODE ###

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


def get_divisor(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if n // i != i:
                divisors.append(n // i)

    return sorted(divisors)


divisors = get_divisor(M)
for d in divisors:
    if d >= N:
        print(M // d)
        exit()

print(1)
### BUGGY CODE ###

import copy

N = int(input())
K = list(map(int,input().split()))
"""
N = 4
K = [1, 2 ,3 ,4]
"""
a = list(set(K))
#print(a)
a_count = {}

for i in a :
    a_count[i] = K.count(i)

#print(a_count)

ans_dict = {}
for i in a_count :

    a_count_2 = copy.deepcopy(a_count)
    
    a_count_2[i] -= 1

    #print(a_count_2)
    
    ans_dict[i] = 0
    for l in a_count_2.values() :
        
        ans_dict[i] += l * (l-1)  // 2

#print(ans_dict)

for i in K:
    print(ans_dict[i])
    pass

### FIXED CODE ###

import copy
from collections import Counter

N = int(input())
K = list(map(int,input().split()))
"""
N = 4
K = [1, 2 ,3 ,4]
"""
a = list(set(K))
#print(a)
a_count = {}



a_count = Counter(K)
#print(c)

#print(a_count)

ans_dict = 0
for l in a_count.values() :
        
    ans_dict += l * (l-1)  // 2

#print(ans_dict)

"""
for i in a_count :

    a_count_2 = copy.deepcopy(a_count)
    
    a_count_2[i] -= 1

    #print(a_count_2)
    
    ans_dict[i] = 0
    for l in a_count_2.values() :
        
        ans_dict[i] += l * (l-1)  // 2

#print(ans_dict)
"""

for i in K:
    print(ans_dict - (a_count[i]-1))
    pass
### BUGGY CODE ###

import numpy as np

N, K = [int(x) for x in input().split()]
A = list([int(x) for x in input().split()])

before = 1

for i in range(K):
    before *= A[i]

for i in range(K, N):
    after = before // A[i-K]
    after *= A[i]

    if after > before:
        print('Yes')
    else:
        print('No')

    before = after


### FIXED CODE ###

N, K = [int(x) for x in input().split()]
A = list([int(x) for x in input().split()])

for i in range(K, N):
    if A[i] / A[i-K] > 1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

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

ans = 0

for b in B:
    ans += len(list(filter(lambda x: x < b, A))) * \
        len(list(filter(lambda x: x > b, C)))

print(ans)


### FIXED CODE ###

from itertools import accumulate

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

acc_a = [0]*N
acc_c = [0]*N

i_a = 0
i_c = N-1
for i in range(N):
    b = B[i]
    while i_a < N and A[i_a] < b:
        acc_a[i] += 1
        i_a += 1

for i in reversed(range(N)):
    b = B[i]
    while i_c >= 0 and C[i_c] > b:
        acc_c[i] += 1
        i_c -= 1

acc_a = list(accumulate(acc_a))
acc_c = list(accumulate(acc_c[::-1]))
acc_c = acc_c[::-1]

ans = 0
for a, c in zip(acc_a, acc_c):
    ans += a*c
print(ans)
### BUGGY CODE ###

import collections
n,k = map(int, raw_input().split(' '))
ais = map(int ,raw_input().split(' '))
for _ in range(k):

	h = collections.Counter()
	for i,d in enumerate(ais):
		u = i+1
		h[max(1, u - d)] += 1
		h[u + d + 1] -= 1

	cumul = 0
	for u in range(1, n+1):
		cumul += h[u]
		ais[u - 1] = cumul

for e in ais:print e,


### FIXED CODE ###

import collections
n,k = map(int, raw_input().split(' '))
ais = map(int ,raw_input().split(' '))

prev = ais[::]
for _ in range(k):

	h = collections.Counter()
	for i,d in enumerate(ais):
		u = i+1
		h[max(1, u - d)] += 1
		h[u + d + 1] -= 1

	cumul = 0
	for u in range(1, n+1):
		cumul += h[u]
		ais[u - 1] = cumul
	if prev == ais[::]:
		break
	prev = ais[::]


for e in ais:print e,
### BUGGY CODE ###

n,m = list(map(int,input().split()))
d = []
s = 1<<0
for i in range(m):
  a,b = list(map(int,input().split()))
  d.append( ((1<<a)-1) ^ ((1<<b)-1) )

ans = float('inf')
for bit in range(1<<n):
    spr = [True]*m
    for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
    if sum(spr) == 0:
      ans = min(ans, sum([1 for i in range(n) if bit & 1<<i]))
      print(ans)
      exit()


### FIXED CODE ###


n,m = list(map(int,input().split()))
d = [0]*m
spr = [True]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = [a,b]

d = sorted(d)
pre = d[0][1]
ans = 1
for i,(a,b) in enumerate(d):
  if a < pre:
    if b < pre:
      pre = b
  else:
    ans += 1
    pre = b

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

from collections import Counter
N, P = map(int, input().split())
S = input()

ans = 0
if P in [2, 5]:
    for i, c in enumerate(S):
        if int(c) % P == 0:
            ans += i + 1
else:
    ct = Counter()
    ct[0] = 1
    for i in range(N-1, -1, -1):
        n = int(S[i:])
        mod = n % P
        ans += ct[mod]
        ct[mod] += 1
print(ans)

### FIXED CODE ###

from collections import Counter
N, P = map(int, input().split())
S = input()

ans = 0
if P in [2, 5]:
    for i, c in enumerate(S):
        if int(c) % P == 0:
            ans += i + 1
else:
    ct = Counter()
    ct[0] = 1
    prevmod = 0
    mods = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    for i in range(N-1, -1, -1):
        n = int(S[i])
        mod = (mods[n] + prevmod) % P
        ans += ct[mod]
        ct[mod] += 1
        prevmod = mod
        mods = [10 * a % P for a in mods]
print(ans)
### BUGGY CODE ###

import math

N = int(input())

sum = 0
for i in range(1, N+1):
  for j in range(1, N+1):
    for k in range(1, N + 1):
      sum+= math.gcd(i,math.gcd(j,k))

print(sum)


### FIXED CODE ###

from math import gcd

N = int(input())

sum = 0
for i in range(1, N+1):
  for j in range(1, N + 1):
    x=gcd(i,j)
    for k in range(1, N + 1):
      hoge = gcd(x,k)
      sum+=hoge

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

# encoding: utf-8
N, M = list(map(int, input().split()))

# TLE
# Amod = [A for A in map(lambda x: int(x) % M , input().split())]
# ans = 0
# for l in range(len(Amod)):
#     acm = 0
#     for r in range(l, len(Amod)):
#         acm = (acm + Amod[r]) % M
#         if acm == 0: ans += 1

# Asym = []

# sym = 0
# cnt_zero = 0
# for i, A in enumerate(map(int, input().split())):
#     sym = (sym + A) % M
#     if sym > 0: Asym.append(sym)
#     else: cnt_zero += 1
    
# ans = cnt_zero * (cnt_zero + 1)
# for sym in set(Asym):
#     Asym.remove(sym)

# for sym in set(Asym):
#     cnt = Asym.count(sym)
#     ans += cnt * (cnt + 1)
        
# print(int(ans / 2))

Acnt = [0 for i in range(M)]
sym = 0

for A in map(int, input().split()):
    sym = (sym + A) % M
    Acnt[sym] += 1

print(int(Acnt[0] + sum([Acnt.count(i) * i * (i - 1) for i in range(1 + max(Acnt))]) / 2))

### FIXED CODE ###

# encoding: utf-8
N, M = list(map(int, input().split()))

d_sym = {}
sym = 0

# refresh

ans = 0
for A in map(int, input().split()):
    sym = (sym + A) % M
    #
    if sym == 0: ans += 1
    # 
    if str(sym) in d_sym.keys(): d_sym[str(sym)] += 1
    else: d_sym[str(sym)] = 1

print(int(ans + sum([val * (val - 1) / 2 for val in d_sym.values()])))
### BUGGY CODE ###

N, Q = map(int, input().split())
town = [[] for _ in range(N)]
for i in range(Q):
    place, year = map(int, input().split())
    tmp = []
    tmp.append(year)
    tmp.append(i)
    town[place-1].append(tmp)

ans = []

for item in town:
    index = town.index(item)
    item.sort()
    index += 1
    index = str(index)
    while len(index) < 6:
        index = '0' + index
    for i in range(len(item)):
        num = i + 1
        num = str(num)
        while len(num) < 6:
            num = '0' + num
        xxx = index + num
        tmp = []
        tmp.append(item[i][1])
        tmp.append(xxx)
        ans.append(tmp)

ans.sort()
for item in ans:
    print(item[1])


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
town = [[] for _ in range(N)]
for i in range(Q):
    place, year = map(int, input().split())
    town[place-1].append([year,i])

# print(town)

ans = []
k = 0
for item in town:
    index = k
    # index = town.index(item)
    # print(item)
    item.sort()
    index = str(index+1)
    while len(index) < 6:
        index = '0' + index
    for i in range(len(item)):
        num = str(i+1)
        while len(num) < 6:
            num = '0' + num
        xxx = index + num
        ans.append([item[i][1],xxx])
    k += 1

ans.sort()
for item in ans:
    print(item[1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A_large = A * 2
rain = []
S = sum(A)
check = 1
while len(rain) != N:
    sub = sum(A_large[check:check + N - 1:2])
    rain.append(S - sub * 2)
    check += 1
for _ in rain:
    print(_)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
rain = []
S = sum(A)
sub = sum(A[1:N:2])
rain.append(S - sub * 2)
while len(rain) != N:
    rain.append(A[len(rain) - 1] * 2 - rain[-1])
for _ in rain:
    print(_)
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
    q = list(input().split())
    if int(q[0]) == 1:
        S = S[::-1]
    else:
        if int(q[1]) == 1:
            S = q[2] + S
        else:
            S = S + q[2]
print(S)

### FIXED CODE ###

from collections import deque
S = list(input())
S = deque(S)
Q = int(input())
c = 0
for _ in range(Q):
    q = list(input().split())
    if int(q[0]) == 1:
        if c == 0:
            c = 1
        else:
            c = 0
    else:
        if c == 0:
            if int(q[1]) == 1:
                S.appendleft(q[2])
            else:
                S.append(q[2])
        else:
            if int(q[1]) == 2:
                S.appendleft(q[2])
            else:
                S.append(q[2])
S = list(S)
if c == 0:
    print("".join(S))
else:
    S = S[::-1]
    print("".join(S))
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for m in range(M):
    B, C = map(int, input().split())
    NA = A + [C] * B
    NA.sort()
    NA = NA[B:]
    A = NA
print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
p = [(A[i], 1) for i in range(N)]
for m in range(M):
    B, C = map(int, input().split())
    p.append((C, B))

p.sort()
p.reverse()

ans = 0
for v, n in p:
    use = min(N, n)
    ans += use * v
    N -= use
    if N == 0:
        break
print(ans)
### BUGGY CODE ###

N = int(input())
D = {}
for _ in range(N):
    x = input()
    if x in D:
        D[x] = D[x] + 1
    else:
        D[x]=1
MaxDarray = [k for k, v in D.items() if v == max(D.values())]
print("\n".join(sorted(MaxDarray)))


### FIXED CODE ###

N = int(input())
L = []
D = {}
for _ in range(N):
    x = input()
    L.append(x)

for x in L:
    D[x] = 0
    
for x in L:
    D[x] += 1

SortD = sorted(D.items(), key=lambda x:x[1])
maxD = SortD[-1][1]
ans = []
for x in reversed(SortD):
    if x[1] == maxD:
        ans.append(x[0])
    else:
        break
for x in sorted(ans):
    print(x)
### BUGGY CODE ###

N, M = map(int, input().split())
ab_list = [list(map(int, input().split())) for i in range(M)]

ab_list.sort()

end_list = list(filter(lambda x: x[1] == N, ab_list))

res = False

for end in end_list:
    if end[0] == 1:
        res = True
        break

if not res:
    for end in end_list:
        if res:
            break
        for ab in list(filter(lambda x: x[1] == end[0], ab_list)):
            if ab[0] == 1:
                res = True
                break

if res:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

N, M = map(int, input().split())
ab_list = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

lis = [[] for i in range(N)]

for i in range(M):
    lis[ab_list[i][0]].append(ab_list[i][1])

que = [[0, 0, lis[0], []]]
ends = []
res = False

while que:
    count, now, next_nodes, visited = que.pop()
    visited.append(now)
    if now == N - 1:
        ends = visited[:]
    for node in next_nodes:
        if node in visited or count == 2:
            continue
        que.append([count + 1, node, lis[node], visited[:]])

if N - 1 in ends:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import defaultdict
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba

def run():
    H, N = map(int, sysread().split())
    AB = []
    for i in range(N):
        a,b = map(int, sysread().split())
        AB.append((a,b))

    INF = float('inf')
    dp = [[INF] * (2*H+2) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(2*H+2):
            tmp = j - AB[i][0]
            if tmp >= 0:
                dp[i+1][j] = min([dp[i][j], dp[i+1][tmp] + AB[i][1]])
            elif j == H and tmp < 0:
                dp[i + 1][H] = min(dp[i][H], dp[i + 1][0] + AB[i][1])
            else:
                dp[i+1][j] = dp[i][j]
    ret = min(dp[N][H:])
    print(ret)



if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import defaultdict
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba

def run():
    H, N = map(int, sysread().split())
    AB = list(map(int, read().split()))
    A = AB[::2]
    B = AB[1::2]
    Amax = max(A)

    INF = float('inf')
    dp = [[INF] * (H+Amax+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H+Amax+1):
            tmp = j - A[i]
            if tmp >= 0:
                dp[i+1][j] = min([dp[i][j], dp[i+1][tmp] + B[i]])
            elif j == H and tmp < 0:
                dp[i + 1][H] = min(dp[i][H], dp[i + 1][0] + B[i])
            else:
                dp[i+1][j] = dp[i][j]
    ret = min(dp[N][H:])
    print(ret)



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

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

W = read().rstrip()

N = len(W)

def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N=len(S)
    arr = [0]*N
    arr[0] = N
    i,j = 1,0
    while i<N:
        while i+j<N and S[j]==S[i+j]:
            j += 1
        arr[i]=j
        if not j:
            i += 1
            continue
        k = 1
        while i+k<N and k+arr[k]<j:
            arr[i+k] = arr[k]
            k += 1
        i += k; j -= k
    return arr

def is_periodic_left(W):
    Z = Z_algorithm(W)
    is_periodic = [False] * N
    for p in range(1,N//2 + 10):
        for i in range(p,N,p):
            if Z[i] >= p:
                is_periodic[p + i - 1] = True
            else:
                break
    return is_periodic

L = is_periodic_left(W)
R = is_periodic_left(W[::-1])[::-1]

if not L[-1]:
    answer = (1,1)
elif len(set(W)) == 1:
    answer = (N,1)
else:
    x = sum(not(x or y) for x,y in zip(L,R[1:]))
    answer = (2,x)
print('\n'.join(map(str,answer)))

### FIXED CODE ###

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

W = list(map(int,read().rstrip()))

N = len(W)

def Z_Algorithm(S):
    # 共通接頭辞の長さを返す
    N=len(S)
    arr = [0]*N
    arr[0] = N
    i,j = 1,0
    while i<N:
        while i+j<N and S[j]==S[i+j]:
            j += 1
        arr[i]=j
        if not j:
            i += 1
            continue
        k = 1
        while i+k<N and k+arr[k]<j:
            arr[i+k] = arr[k]
            k += 1
        i += k; j -= k
    return arr

def find_good_substr(W):
    Z = Z_Algorithm(W)
    is_good = [True]*(N+1) # 長さをインデックス
    for n in range(1,N//2+1):
        # n文字での周期をもってくる
        if not is_good[n]:
            continue
        for i in range(n+n,Z[n]+n+1,n):
            is_good[i] = False
    return is_good

def solve():
    G1 = find_good_substr(W)
    G2 = find_good_substr(W[::-1])[::-1]
    if G1[-1]:
        # 自分自身がoptimal
        return 1,1
    if len(set(W)) == 1:
        return N,1
    # 2個にできるはず
    x = sum(x and y for x,y in zip(G1[1:-1],G2[1:-1]))
    return 2,x

x,y = solve()
print(x)
print(y)
### BUGGY CODE ###

n, q = (int(i) for i in input().split())
s = input()
e = [[int(i)-1 for i in input().split()] for i in range(q)]

for x in e:
    print(s[x[0]:x[1]+1].count("AC"))


### FIXED CODE ###

# 高速版input
import sys
input = sys.stdin.readline

n, q = (int(i) for i in input().split())
s = input()

mem = [0]
count = 0
for i in range(1, len(s)):
    if s[i-1]+s[i] == "AC":
        count +=1
    mem.append(count)
    
for x in [[int(i)-1 for i in input().split()] for i in range(q)]:
    res = mem[x[1]] - mem[x[0]]
    print(res)
### BUGGY CODE ###

import math

def combinations_count(n, r):
    a = 1
    b = 1
    if (n != 0) & (n >= r):
        for i in range(n, n - r, -1):
            a *= i
            b *= i - n + r
        return a // b
    else:
        return 0

n, k = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
mod = 10 ** 9 + 7
ans = 0
for index, value in enumerate(a):
    ans += (combinations_count(index, k - 1) - combinations_count(n - index - 1, k - 1)) * value % mod
print(ans % mod)

### FIXED CODE ###

n, k = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
mod = 10 ** 9 + 7
ans = 0

f = [1] * (n + 1)
inv = [1] * (n + 1)
for i in range(1, n + 1):
    f[i] = (f[i - 1] * i) % (mod)
inv[n] = pow(f[n], mod - 2, mod)
for i in range(n - 1, 0, -1):
    inv[i] = inv[i + 1] * (i + 1) % mod

def combination(n, r):
    if (n != 0) & (n >= r):
        return f[n] * inv[r] * inv[n - r] % mod
    return 0    
    
ans = 0
for index, value in enumerate(a):
    ans += (combination(index, k - 1) - combination(n - index - 1, k - 1)) * value
print(ans % mod)
### BUGGY CODE ###

def s():return int(input())
def mp():return map(int,input().split())
# a =s()
# b =s()
# ans = ""
# for i in range(len(b)):
# 	ans+=b[i]
# 	if ans in a:
# 		pass
# 	else:
# 		print(len(b)-i)
# 		break

a = s()
b = list(mp())
ans=0
for i in range(a):
	for j in range(i+1,a):
		ans+=b[i]*b[j]
		ans%=((10**9)+7)
print(ans)

### FIXED CODE ###

def s():return int(input())
def mp():return map(int,input().split())
a = s()
b = list(mp())
ans=0
t = sum(b)%(10**9+7)
for i in range(a):
	t-=b[i]
	ans+=b[i]*t
	ans%=(10**9+7)
print(ans)
### BUGGY CODE ###

import sys
import queue
s = list(map(str,input()))
t = list(map(str,input()))

if len(set(s) & set(t)) < len(set(t)):
    print(-1)
    sys.exit()

q = queue.Queue()
for i in range(len(s)):
    q.put(s[i])
w = t[::-1]

ans = 0
while len(w) > 0:
    a = q.get()
    b = w.pop()
    if a != b:
        w.append(b)
    q.put(a)
    ans += 1
print(ans)

### FIXED CODE ###

from bisect import bisect_right, bisect_left
s = [ord(i) - ord("a") for i in input()]
t = [ord(i) - ord("a") for i in input()]
index = [[] for _ in range(26)]

for i, x in enumerate(s):
    index[x].append(i)


l_s = len(s)

for x in index:
    if x:
        x.append(x[0] + l_s)

cnt = -1
for r in t:
    seq = index[r]
    if not seq:
        cnt = -2
        break
    i = cnt % l_s
    j = bisect_right(seq, i)
    cnt += seq[j] - i

print(cnt+1)