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

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

L = sorted(L, reverse=True)
ans = 0

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if L[i] < L[j] + L[k]:
                ans += 1
            else:
                break

print(ans)


# for i in range(N - 2):
#     if L[i] < L[i + 1] + L[i + 2] and L[i + 1] < L[i + 2] + \
#             L[i] and L[i + 2] < L[i] + L[i + 1]:
#         ans += 1

# print(ans)


### FIXED CODE ###

import bisect
N = int(input())
L = [int(i) for i in input().split()]

SL = sorted(L)
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        right = bisect.bisect_left(SL, SL[i] + SL[j])
        left = j + 1
        ans += right - left

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

import copy, math

n = int(input())
a = input().split()

result = []

num_dict = {}

for x in set(a):
    num_dict[x] = a.count(x)

def calc(x):
    if x >= 2:
        return math.factorial(x) / (math.factorial(x - 2) * 2)
    else:
        return 0

for i in range(len(a)):
    result = 0

    temp_num_dict = copy.copy(num_dict)

    temp_num_dict[a[i]] -= 1

    for x in num_dict.keys():
        result += calc(temp_num_dict[x])

    print(int(result))

### FIXED CODE ###

#%%
import copy, math, collections

n = int(input())
a = input().split()

result = []

num_dict = dict(collections.Counter(a))

def calc(x):
    if x >= 2:
        return math.factorial(x) / (math.factorial(x - 2) * 2)
    else:
        return 0

result_dict = {}
result_minus1_dict = {}

for key, value in num_dict.items():
    result_dict[key] = calc(num_dict[key])
    result_minus1_dict[key] = calc(num_dict[key] - 1)

result_all = sum(result_dict.values())

for i in range(len(a)):
    print(int(result_all - result_dict[a[i]] + result_minus1_dict[a[i]]))

# %%
### BUGGY CODE ###

n,q=map(int,input().split())
event=[]

for _ in range(n):
    s,t,x=map(int,input().split())
    event.append([s-x,1,x])
    event.append([t-x,-1,x])
event.sort()
d=[int(input()) for _ in range(q)]

k=0
stop={}
for i in range(q):
    while k<2*n and event[k][0]<=d[i]:
        if event[k][1]==1: stop[event[k][2]]=1
        else: stop.pop(event[k][2])
        k+=1
    print(min(stop) if stop!={} else -1)

### FIXED CODE ###

def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)

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

    event=[]
    for _ in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,1,x))
        event.append((t-x,-1,x))

    for i in range(q):
        event.append((int(input()),2,i))
    event.sort()

    ans=[0]*q

    stop=set()
    hq=[]
    for t,op,x in event:
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)

        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

main()
### BUGGY CODE ###

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

count=1
ans = 0
while (a+b)*count<=n:
    ans +=a
    count+=1
    # print(count)
r = n - (a+b)*(count-1)
# print(r)
if not r == 0:
    ans += min([a,r])
print(ans)

### FIXED CODE ###

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

q = int(n/(a+b))
r = n - (a+b)*(q)
ans = q*a
ans += min([a,r])
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
sys.stdin.readline
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e = sorted(e)
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    imos.append((s-x,x))
    imos.append((t-x,-x))
ans = set()
j = 0
for i in range(q):
    d = int(input())
    imos.append((d,1e100))
imos.sort()
m = 1e100
flag = False
for t,stop in imos:
    if stop == 1e100:
        if ans:
            if not flag:
                m = min(ans)
                flag = True
            print(m)
        else:
            print(-1)
    elif stop > 0:
        ans.add(stop)
        if stop < m:
            m = stop
            flag = True
    else:
        ans.remove(-stop)
        if m == -stop:flag = False
### BUGGY CODE ###

import sys

def resolve(in_):
    H, W, M = map(int, next(in_).split())
    targets = tuple(tuple(map(int, line.split())) for line in in_)
    # H, W, M = 3, 3, 3
    # targets = ((1, 1), (2, 1), (1, 3))
    
    target_h = {}
    target_w = {}
    target_hw = set()
    for h, w in targets:
        target_h[h - 1] = target_h.setdefault(h - 1, 0) + 1
        target_w[w - 1] = target_w.setdefault(w - 1, 0) + 1
        target_hw.add((h - 1, w - 1))

    ans = 0
    for h, a in target_h.items():
        for w, b in target_w.items():
            ans = max(ans, target_h[h] + target_w[w] - (1 if (h, w) in target_hw else 0))
    
    return ans

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import itertools


def resolve(in_):
    H, W, M = map(int, next(in_).split())
    targets = tuple(tuple(map(int, line.split())) for line in in_)
    
    target_h = {}
    target_w = {}
    target_hw = set()
    for h, w in targets:
        target_h[h] = target_h.setdefault(h, 0) + 1
        target_w[w] = target_w.setdefault(w, 0) + 1
        target_hw.add((h, w))

    max_h = max(target_h.values())
    max_w = max(target_w.values())

    h_set = {h for h, v in target_h.items() if max_h == v}
    w_set = {w for w, v in target_w.items() if max_w == v}

    ans = max_h + max_w - 1
    for hw in itertools.product(h_set, w_set):
        if hw not in target_hw:
            ans += 1
            break
    
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


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

h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]

iti = [[] for _ in range(h*w + 1)]

for h_ in range(h):
    for w_ in range(w):
        iti[a[h_][w_]].append(w_+1)
        iti[a[h_][w_]].append(h_+1)


def query(l, r):
    cost = 0
    now = iti[l]
    while l < r:
        next = iti[l + d]
        cost += abs(now[0] - next[0]) + abs(now[1] - next[1])
        l += d
        now = iti[l]
    return cost


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, r))


### FIXED CODE ###

h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]

iti = [[] for _ in range(h*w + 1)]

for h_ in range(h):
    for w_ in range(w):
        iti[a[h_][w_]].append(w_+1)
        iti[a[h_][w_]].append(h_+1)

#累積和的なやつ
s_d = [[] for _ in range(d+1)]
for i in range(1, d+1): # i:= スタート位置　1からｄまである
    now = i
    s_d[i].append(0) # スタート位置のコストは０
    while now + d <= h*w:
        s_d[i].append(s_d[i][-1] + abs(iti[now][0]-iti[now+d][0]) + abs(iti[now][1]-iti[now+d][1]))
        now += d
#print(s_d)

def query(l, r):
    idx = l % d # スタート位置 = idx　
    if idx == 0:
        idx = d
    # s_d[idx]の配列を使用
    # l, rをs_d[idx]上のインデックスに合わせる
    l_d = l // d
    r_d = r // d
    if l % d == 0:
        l_d -= 1
        r_d -= 1
    cost = s_d[idx][r_d] - s_d[idx][l_d]
    return cost


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, r))
### BUGGY CODE ###

K, S = map(int,input().split())
ans = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k == S:
                ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int,input().split())
ans = 0
for x in range(K+1):
    for y in range(K+1):
        z = S-x-y
        if 0 <= z and z <= K:
            ans += 1
print(ans)
### BUGGY CODE ###

import bisect
n = int(input())
a = [int(input()) for i in range(n)]

color_num = [a[0]]
cnt = 1
for i in range(1, n):
    temp = bisect.bisect_left(color_num, a[i])
    if cnt == temp:
        color_num[temp - 1] = a[i]
    elif temp == 0:
        color_num = [a[i]] + color_num
        cnt += 1
    else:
        color_num[temp - 1] = a[i]

print(cnt)


### FIXED CODE ###

import bisect
n = int(input())
a = [int(input()) for i in range(n)][::-1]

color_num = [a[0]]
for i in range(1, n):
    if a[i] >= color_num[-1]:
        color_num.append(a[i])
    else:
        temp = bisect.bisect_right(color_num, a[i])
        color_num[temp] = a[i]


print(len(color_num))
### BUGGY CODE ###

LR = list(map(int,input().split()))
L = LR[0]
R = LR[1]
K = 2018
for j in range(L,R+1):
    for i in range(L,j):
        if K > (i*j)%2019:
            K =  (i*j)%2019
print(K)

### FIXED CODE ###

LR = list(map(int,input().split()))
L = LR[0]
R = LR[1]
K = 2018
if R - L> 2019:
    K = 0
else:
    for j in range(L,R+1):
        for i in range(L,j):
            if K > (i*j)%2019:
                K =  (i*j)%2019
print(K)
### BUGGY CODE ###

def main():
    N = int(input())
    S_list = []
    for _ in range(N):
        S_list.append(input())

    S_dict = {}
    for s in S_list:
        S_dict[s]=0
    for s in S_list:
        S_dict[s]+=1



    max_k_list = [kv[0] for kv in S_dict.items() if kv[1] == max(S_dict.values())]
    max_k_list.sort()
    for k in max_k_list:
        print(k)

if __name__ == '__main__':
     main()

### FIXED CODE ###

def main():
    N = int(input())
    S_list = []
    for _ in range(N):
        S_list.append(input())

    S_dict = {}
    for s in S_list:
        S_dict[s]=0
    for s in S_list:
        S_dict[s]+=1

    max_v = max(S_dict.values())

    max_k_list = [kv[0] for kv in S_dict.items() if kv[1] == max_v]
    max_k_list.sort()
    for k in max_k_list:
        print(k)

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

import numpy as np
H, W, K = map(int,input().split())
S = [list(map(int,input())) for _ in range(H)]
S = np.array(S)
ans = float("inf")
for i in range(1<<(H - 1)):
    data = np.array([[0] * W for _ in range(H)])
    data[0] += S[0]
    ind = 0
    for j in range(H - 1):
        if (i >> j) & 1:
            ind += 1
        data[ind] += S[j + 1]
    if np.max(data) > K:
        continue
    cnt = ind
    judge = np.array([0] * (ind + 1))
    for j in range(W):
        judge += data[:(ind + 1),j]
        if np.max(judge) > K:
            judge = np.array(data[:(ind + 1),j])
            cnt += 1
    ans = min(ans, cnt)
print(ans)

### FIXED CODE ###

H, W, K = map(int,input().split())
S = [list(map(int,input())) for _ in range(H)]
ans = float("inf")
for i in range(1<<(H - 1)):
    data = [S[0][0:]]
    for j in range(H - 1):
        if (i >> j) & 1:
            data.append([0] * W)
        for k in range(W):
            data[-1][k] += S[j + 1][k]
    if any([any([x > K for x in y]) for y in data]):
        continue
    cnt = len(data) - 1
    judge = [0] * len(data)
    for j in range(W):
        if any([judge[x] + data[x][j] > K for x in range(len(data))]):
            judge = [0] * len(data)
            cnt += 1
        judge = [judge[x] + data[x][j] for x in range(len(data))]
    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

N=int(input())
sum=0
for i in range(N):
    sum+=i
if N==1:
    print(0)
else:
    print(sum)

### FIXED CODE ###

N=int(input())-1
sum=(N*(N+1))//2
if N==0:
    print(0)
else:
    print(sum)
### BUGGY CODE ###

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

Ls = list(set(ls))
Ls.sort()

if len(Ls) < 3:
  print(0)
else:
  ans = 0
  LsR = sorted(Ls)
  while len(LsR) >= 3:
    L1 = LsR[0]
    Ls1 = LsR[1:]
    while len(Ls1) >= 2:
      L2 = Ls1[0]
      Ls2 = Ls1[1:]
      for L3 in Ls2:
        if L3 < L1 + L2 and L3 > abs(L1-L2):
          n1 = sum([l == L1 for l in ls])
          n2 = sum([l == L2 for l in ls])
          n3 = sum([l == L3 for l in ls])
          ans += n1 * n2 * n3
      Ls1 = Ls1[1:]
    LsR = LsR[1:]
  print(ans)

### FIXED CODE ###

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

import collections
c = collections.Counter(ls)

Ls = list(set(ls))
Ls.sort()

if len(Ls) < 3:
  print(0)
else:
  ans = 0
  LsR = sorted(Ls)
  while len(LsR) >= 3:
    L1 = LsR[0]
    Ls1 = LsR[1:]
    while len(Ls1) >= 2:
      L2 = Ls1[0]
      Ls2 = Ls1[1:]
      for L3 in Ls2:
        if L3 < L1 + L2 and L3 > abs(L1-L2):
          ans += c[L1] * c[L2] * c[L3]
      Ls1 = Ls1[1:]
    LsR = LsR[1:]
  print(ans)
### BUGGY CODE ###

n, x, y = map(int, input().split())
x -= 1
y -= 1

k = [0 for _ in range(n)]
for i in range(n):
    for j in range(i + 1, n):
        dist = min([j-i, abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(j-x)])
        if dist < n:
            k[dist] += 1
for i in range(1, len(k)):
    print(k[i])


### FIXED CODE ###

n, x, y = map(int, input().split())
x -= 1
y -= 1

k = [0 for _ in range(n)]
for i in range(n):
    for j in range(i + 1, n):
        dist = min(j-i, abs(x-i)+1+abs(j-y))
        if dist < n:
            k[dist] += 1
for i in range(1, len(k)):
    print(k[i])
### BUGGY CODE ###

l, r = [int(x) for x in input().split()]

l_mod = l % 2019
r_mod = r - (l - l_mod)
if l_mod >= r_mod:
    r_mod += 2019

ans = 2019
for i in range(l_mod, r_mod):
    for j in range(i + 1, r_mod + 1):
        tmp = (i * j) % 2019
        if tmp < ans:
            ans = tmp

print(ans)

### FIXED CODE ###

l, r = [int(x) for x in input().split()]

l_mod = l % 2019
if r - l >= 2019:
    r_mod = l_mod + (r - l - 2019) % 2019 + 2019
else:
    r_mod = l_mod + (r - l) % 2019

ans = 2019
for i in range(l_mod, r_mod):
    for j in range(i + 1, r_mod + 1):
        tmp = (i * j) % 2019
        if tmp < ans:
            ans = tmp

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

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*(10**(i))%13)%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*(10**(i))%13)%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*(10**(i))%13)%13] += dp[i][k]
                    dp[i+1][(k+l*(10**(i))%13)%13] %= MOD
    print(dp[-1][5])

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

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

N,M,L=map(int,input().split())
G=[[10**15 for i in range(N)] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j]=min(G[i][j],G[i][k]+G[k][j])
H=[[10**15 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j]<=L:
            H[i][j]=1
for k in range(N):
    for i in range(N):
        for j in range(N):
            H[i][j]=min(H[i][j],H[i][k]+H[k][j])
Q=int(input())
for line in range(Q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if H[s][t]==10**15:
        print(-1)
    else:
        print(H[s][t]-1)


### FIXED CODE ###

N,M,L=map(int,input().split())
G=[[10**15 for i in range(N)] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j]=min(G[i][j],G[i][k]+G[k][j])
H=[[10**15 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j]<=L:
            H[i][j]=1
for k in range(N):
    for i in range(N):
        for j in range(N):
            H[i][j]=min(H[i][j],H[i][k]+H[k][j])
Q=int(input())
for line in range(Q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if H[s][t]==10**15:
        print(-1)
    else:
        print(H[s][t]-1)
### BUGGY CODE ###

import heapq
n, m = [ int(v) for v in input().split() ]
num_list = sorted([ -int(v) for v in input().split() ])

for i in range(m):
	a, b = [ int(v) for v in input().split() ]
	for j in range(a):
		heapq.heappush(num_list,-b)

ans = 0
for i in range(n):
	ans += heapq.heappop(num_list)

print(-ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def swap(a):
    return ((a[1],a[0]))


n, m = [ int(v) for v in input().split() ]
num_list = [ (int(v), 1) for v in input().split() ]
change_list = [ swap([ int(v) for v in input().split() ]) for i in range(m) ]
total_list = sorted(num_list + change_list, reverse = True)

k = n
ans = 0

for i in total_list:

    j = min(i[1], k)
    k -= j
    ans += i[0] * j
    if k == 0:
        break
print(ans)
### BUGGY CODE ###

#170D
def main():
    import sys, random
    from collections import Counter
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    #print(random.randint(1, 10**6))
    #A = [random.randint(1, 10**6) for _ in range(2*(10**3))]
    B = Counter(A)
    #print(B)
    A = list(set(A))
    A.sort()
    #print(A)
    def era(A):
        for i in range(len(A)):
            for j in range(len(A)-1, i, -1):
                if A[j] % A[i] ==0:
                    A.pop(j)
    
    era(A)
    #print(A)
 
    
    for i in range(len(A)-1, -1, -1):
        if B[A[i]]>=2:
            A.pop(i)
    #print(dp)
    print(len(A))
    
 
 
if __name__=='__main__':
    main()

### FIXED CODE ###

#170D
def main():
    import sys
    from collections import Counter
    import random
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    #A = [random.randint(1, 10**6+1) for _ in range(2*(10**5))]
    judge = [0 for _ in range(10**6+1)]
    A.sort()
    B = Counter(A)
    for a in A:
        judge[a] =1
    for a in A:
        if judge[a] ==1:
            if B[a] >=2:
                judge[a] = 0
            for i in range(2*a, 10**6+1, a):
                judge[i] = 0
                
    print(judge.count(1))

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

import sys
import math
import copy
a = int(input());
b = [int(input()) for i in range(a)];
c = 0;
f = max(b);
for i in range(a):
    if max(b) > b[i]:
        print(f);
    elif max(b) == b[i]:
        d = copy.copy(b);
        del d[i]
        e = max(d);
        print(e);


### FIXED CODE ###

import sys
import math
import copy
a = int(input());
b = [int(input()) for i in range(a)];
c = 0;
first = max(b);
g = b.copy();
h = g.index(first);
del g[h];
second = max(g);

for i in range(a):
    if first > b[i]:
        print(first);
    elif first == b[i]:
        print(second);
### BUGGY CODE ###

def solve(A, i, m, n):
    """Return if it is possible to make value m with some elements in A.

    n is length of A.
    i is index.
    Using Divide-and-Conquer method.
    """

    if m == 0:
        return True
    if i >= n:
        return False
    if m < 0:
        return False
    return solve(A, i + 1, m, n) or solve(A, i + 1, m - A[i], n)


n = int(input())

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

x = input()

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

for m in M:
    if solve(A, 0, m, n):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

def solve(A, i, m, n):
    """Return if it is possible to make value m with some elements in A.

    n is length of A.
    i is index.
    R is the record of answer i, m.
    Using Divide-and-Conquer method.
    """

    if R[i][m] != None:
        return R[i][m]
    if m == 0:
        R[i][m] = True
        return True
    elif i >= n:
        R[i][m] = False
        return False
    else:
        ans = solve(A, i + 1, m, n) or solve(A, i + 1, m - A[i], n)
        R[i][m] = ans
        return ans


import sys

n = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
q = int(sys.stdin.readline())
M = tuple(map(int, sys.stdin.readline().split()))

s_A = sum(A)
R = [[None] * 2000 for i in range(n + 1)]

ans = ''

for m in M:
    if s_A < m:
        ans += 'no\n'
    elif solve(A, 0, m, n):
        ans += 'yes\n'
    else:
        ans += 'no\n'

print(ans, end = '')
### BUGGY CODE ###

s = input()
t = input()
n = len(s)

dict_s = {}
for i, c in enumerate(s * 2):
    dict_s[c] = dict_s.get(c, []) + [i]


# dict_next_i = {
#     c: [min(j for j in dict_s[c] if j > i) for i in range(n)] for c in dict_s.keys()
# }
dict_next_i = {c: [None] * n for c in dict_s.keys()}

for c in dict_s.keys():
    for i in range(n):
        for j in dict_s[c]:
            if j > i:
                dict_next_i[c][i] = j
                break


def next_i(i, c):
    if c not in dict_s.keys():
        return -1
    else:
        return n * (i // n) + dict_next_i[c][i % n]


def answer():
    i = -1
    for c in t:
        i = next_i(i, c)
        if i == -1:
            return -1
    return i + 1  # 1-origin


print(answer())


### FIXED CODE ###

from bisect import bisect_left
from string import ascii_lowercase

s = input()
t = input()
n = len(s)

dict_s = {c: [] for c in ascii_lowercase}
for i, c in enumerate(s * 2):
    dict_s[c].append(i)

for c in ascii_lowercase:
    if not dict_s[c]:
        del dict_s[c]


dict_next_i = {
    c: [dict_s[c][bisect_left(dict_s[c], i + 1)] for i in range(n)]
    for c in dict_s.keys()
}


def next_i(i, c):
    return n * (i // n) + dict_next_i[c][i % n]


def answer():
    if not all(c in s for c in t):
        return -1
    i = -1
    for c in t:
        i = next_i(i, c)
    return i + 1  # 1-origin


print(answer())
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    ans *= a[i]
if ans > 10 ** 18:
    ans = '-1'
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    ans *= a[i]
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

from collections import Counter

N, K = map(int, input().split())
A = list(map(lambda x:int(x)-K, input().split()))
A.sort()

M = []
P = []
zero = 0
for a in A:
    if a < 0:
        M.append(a)
    elif a > 0:
        P.append(a)
    else:
        zero += 1

def Sum_list(i, s, L, ans):
    if i == len(L):
        ans.append(s)
        return ans
    ans = Sum_list(i+1, s, L, ans)
    ans = Sum_list(i+1, s+L[i], L, ans)
    return ans


SM = Sum_list(0, 0, M, [])
CM = Counter(SM)
SP = Sum_list(0, 0, P, [])
CP = Counter(SP)

ans = 0
for k, v in CP.items():
    if k == 0:
        continue
    if -k in CM.keys():
        ans += CM[-k]*v

print(ans*2**zero+2**zero-1)

### FIXED CODE ###

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

dp = [[[0 for _ in range((N+1)*(L+1))] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for j in range(1, N+1):
    for k in range(N+1):
        for s in range((N+1)*(L+1)):
            if s < X[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            if k >= 1 and s >= X[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-X[j-1]]
ans = 0
for k in range(1, N+1):
    ans += dp[N][k][k*A]
print(ans)