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

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

P = [[x+1] for x in range(N)]
n = [x+1 for x in range(N)]
a = [N*(N-1)/2]

for i in range(M-1):
    if a[i] == 0:
        a.append(0)
    else:        
        p = P[n[A[i][0]-1]-1]
        q = P[n[A[i][1]-1]-1]
        if n[A[i][0]-1] != n[A[i][1]-1]:
            a.append(a[i]-len(p) * len(q))
            if len(p) >= len(q):                
                P[n[A[i][0]-1]-1].extend(q)
                for j in q:
                    n[j-1] = n[A[i][0]-1]
            else:
                P[n[A[i][1]-1]-1].extend(p)
                for j in p:
                    n[j-1] = n[A[i][1]-1]
        else:
            a.append(a[i])
        
for k in range(M):
    print(int(a[::-1][k]))

### FIXED CODE ###

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


P = [[x+1] for x in range(N)]
n = [x+1 for x in range(N)]
an = [N*(N-1)/2]


for i in range(M-1):
    if an[i] == 0:
        an.append(0)
    else:        
        Aind = A[i][0]-1
        Bind = A[i][1]-1
        PAind = P[n[Aind]-1]
        PBind = P[n[Bind]-1]
        if n[Aind] != n[Bind]:
            if len(PAind) >= len(PBind):
                an.append(an[i]-len(PAind) * len(PBind))
                P[n[Aind]-1].extend(PBind)
                for j in PBind:
                    n[j-1] = n[Aind]
            else:
                an.append(an[i]-len(PAind) * len(PBind))
                P[n[Bind]-1].extend(PAind)
                for j in PAind:
                    n[j-1] = n[Bind]
        else:
            an.append(an[i])
            
        
an = an[::-1]
for k in range(M):
    print(int(an[k]))
### BUGGY CODE ###

S = input()
N = len(S)
ans = 0
for i in range(N-3):
    for j in range(i+3, N):
        t = S[i:j+1]
        if int(t) % 2019 == 0:
            #print(i + 1, j + 1)
            ans += 1
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

S = input()
N = len(S)
P = 2019
if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    sys.exit()

num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

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

import sys
def input():
    return sys.stdin.readline()[:-1]

n = int(input())
s = [input() for i in range(n)]
cnt = 0
for i in range(0, n-1):
    s[i] = sorted(s[i])
    for j in range(i+1, n):
        s[j] = sorted(s[j])
        if s[i] == s[j]:
            cnt += 1
print(cnt)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
d = {}
ans = 0
n = int(input())
s = [''.join(sorted(input())) for i in range(n)]
for string in s:
    if string in d:
        ans += d[string]
        d[string] += 1
    else:
        d[string] = 1
print(ans)
### BUGGY CODE ###

def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  x=reversed_num(number.pop())+1
  if x in number:
    number.remove(x)
    count+=1
print(count)


### FIXED CODE ###

import bisect
def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  k=number.pop()
  if len(number)==0:
    break
  if k==int(k):
    x=reversed_num(k)+1
    y=bisect.bisect_left(number,x)
    if x>number[-1]:
      y-=1
    if number[y] ==x:
      number[y]-=0.5
      count+=1
print(count)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
input = sys.stdin.buffer.readline
INF = float("inf")

def main():
    N,M = map(int,input().split())
    A,B,C = [],[],[]
    for i in range(M):
        a,b =map(int,input().split())
        c = list(map(int,input().split()))
        A.append(a)
        B.append(b)
        C.append(c)

    # dp[i][j] : i番目の鍵までを使い, j の組み合わせの箱を開けるのに必要な最小費用
    dp = [[INF for _ in range(2**N)] for _ in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a,b,c = A[i],B[i],C[i]
        bit = 0
        # 開錠可能な箱をbitで表現する
        for x in c:
            bit |= 1 << (x-1)
        for j in range(2**N):
            # 鍵を使う場合
            dp[i+1][j | bit] = min(dp[i+1][j | bit], dp[i][j] + a)
            # 鍵を使わない場合
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    
    if dp[-1][-1] == INF:
        print(-1)
    else:
        print(dp[-1][-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env pypy

import sys
input = sys.stdin.buffer.readline
INF = float("inf")

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

    # dp[i][j] : i番目の鍵までを使い, j の組み合わせの箱を開けるのに必要な最小費用
    dp = [[INF for _ in range(2**N)] for _ in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a,b =map(int,input().split())
        c = list(map(int,input().split()))

        # 開錠可能な箱をbitで表現する
        bit = 0
        for x in c:
            bit |= 1 << (x-1)
        
        for j in range(2**N):
            # 鍵を使う場合
            dp[i+1][j | bit] = min(dp[i+1][j | bit], dp[i][j] + a)
            # 鍵を使わない場合
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    
    if dp[-1][-1] == INF:
        print(-1)
    else:
        print(dp[-1][-1])

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

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

m = [0]*(10**6 + 1)

for i in a:
    if m[i] == 1:
        m[i] = 2
        continue
    tmp = i 
    while tmp <= 10**6:
        m[tmp] += 1
        tmp += i
ans = 0
for i in a:
    if m[i] == 1:
        ans += 1
print(ans)

### FIXED CODE ###

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

ma = max(a)
m = [0]*(ma + 1)

for i in a:
    if m[i] == 1:
        m[i] = 2
        continue
    for j in range(i,ma+1,i):
        m[j]+=1
ans = 0
for i in a:
    if m[i] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())

M = 0

for i in range(1, N):
    M = M + i

print(M)

### FIXED CODE ###

N = int(input())

s = (N-1) * N // 2
print(s)
### BUGGY CODE ###

l=list(input())
n=len(l)
p=10**9+7
ans=0
d=0
for i in range(n):
    if l[i]=="1":
        x=n-i-1
        k=x//p
        m=x%p
        K=d//p
        M=d%p
        ans+=((3**(k+m))%p)*((2**(K+M))%p)
        d+=1
    else:
        continue
K=d//p
M=d%p
ans+=2**(K+M)
print(ans%p)


### FIXED CODE ###

l=list(input())
n=len(l)
p=10**9+7
dp1=[0]*n
dp2=[0]*n
dp1[0]=1
dp2[0]=2
for i in range(1,n):
    if l[i]=="1":
        dp1[i]=(3*dp1[i-1]+dp2[i-1])%p
        dp2[i]=(dp2[i-1]*2)%p
    else:
        dp1[i]=(3*dp1[i-1])%p
        dp2[i]=dp2[i-1]
print((dp1[n-1]+dp2[n-1])%p)
### BUGGY CODE ###

md=10**9+7
n,m=map(int,input().split())
s=list(input().split())
t=list(input().split())
dp=[[0]*(m+3) for _ in range(n+3)]
dp[0][0]=1
for i,sk in enumerate(s):
    for j,tk in enumerate(t):
        if sk==tk:
            dp[i+1][j+1]=sum(sum(dpi[:j+1]) for dpi in dp[:i+1])
print(sum(sum(dpi) for dpi in dp)%md)

### FIXED CODE ###

def f(n, m):
    s = list(input().split())
    t = list(input().split())
    dp = [[1] * (m + 1) for _ in range(n + 1)]
    for i, sk in enumerate(s):
        dpi1 = dp[i + 1] = dp[i][:]
        cs = 0
        for j, tk in enumerate(t):
            if sk == tk:
                cs = (cs + dp[i][j]) % md
            dpi1[j + 1] = (dpi1[j + 1] + cs) % md
#    for x in dp:
#        print(*x)
    print(dp[-1][-1])

md = 10 ** 9 + 7
n, m = map(int, input().split())
f(n, m)
### BUGGY CODE ###

import numpy as np

N,K = map(int,input().split())
P = np.array(list(map(int,input().split())))

ans = 0
for i in range(N-K+1):
    s = (K+ np.sum(P[i:i+K]))/2
    if s > ans:
        ans = s
print(ans)

### FIXED CODE ###

import numpy as np

N,K = map(int,input().split())
P = np.array(list(map(int,input().split())))

s = (K+ np.sum(P[:K]))/2
ans = s
for i in range(1,N-K+1):
    s = s - P[i-1]/2 + P[i+K-1]/2
    if s > ans:
        ans = s
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections
import itertools


def solve(N: int, S: str):

    dp = collections.defaultdict(set)
    for i,s in enumerate(S):
        for k,v in list(dp.items()):
            for vv in v:
                if vv + len(k) == i:
                    dp[k+s].add(vv)
        dp[s].add(i)
    
    dp_sorted = sorted(((k,v) for k,v in dp.items() if len(v) > 1),key=lambda x:len(x[0]),reverse=True)

    for k,v in dp_sorted:
        if max(v) - min(v) >= len(k):
            print(len(k))
            return

    print(0)

def filter_dp(dp):
    return {k:v for k,v in dp.items() if len(v) > 1}

def solve2(N: int, S: str):
    dp = collections.defaultdict(set)

    for i,s in enumerate(S[:-1]):
        dp[S[i:i+2]].add(i)

    dp = filter_dp(dp)

    if len(dp) > 0:
        for i in range(2, N):
            dp2 = collections.defaultdict(set)
            for k,v in dp.items():
                for a, b in itertools.combinations(v,2):
                    a, b = sorted([a,b])
                    if b+i < N and a+i < b and S[a+i] == S[b+i]:
                        dp2[S[a:a+i+1]].add(a)
                        dp2[S[a:a+i+1]].add(b)
            if len(dp2):
                dp = dp2
            else:
                print(i)
                return

    print(0)

    



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve2(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections
import itertools


def solve(N: int, S: str):
    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        if S[i] == S[-1]:
            dp[i][N-1] = 1

    res = 0
    for i in range(N-2,-1,-1):
        for j in range(N-2,i,-1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
                l = dp[i][j]
                if j >= i+l:
                    res = max(res,l)

    print(res)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

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

import itertools
n,m,q=(int(i) for i in input().split())
l=[]
r=[i+1 for i in range(m)]
point=0
def checker(x,l):
  p=0
  for i in range(len(l)):
    a,b,c,d=(l[i][j] for j in range(4))
    if x[b]-x[a]==c:
      p+=d
  return p
for i in range(q):
  a,b,c,d=(int(i) for i in input().split())
  a-=1
  b-=1
  l.append([a,b,c,d])
for i in itertools.combinations_with_replacement(r,n):
  p=checker(i,l)
  if p>point:
    point=p
print(point)


### FIXED CODE ###

import itertools
n,m,q=(int(i) for i in input().split())
l=[]
r=[i+1 for i in range(m)]
point=0
def checker(x,l):
  p=0
  for i in range(len(l)):
    if x[l[i][1]]-x[l[i][0]]==l[i][2]:
      p+=l[i][3]
  return p
for i in range(q):
  a,b,c,d=(int(i) for i in input().split())
  a-=1
  b-=1
  l.append([a,b,c,d])
for i in itertools.combinations_with_replacement(r,n):
  p=checker(i,l)
  if p>point:
    point=p
print(point)
### BUGGY CODE ###

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

for i in range(K+1,N+1):
#  print(A[i-K-1:i-1],A[i-K:i])
  if sum(A[i-K-1:i-1]) < sum(A[i-K:i]):
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
prev = sum(A[0:K])
for i in range(K+1,N+1):
  curr = prev - A[i-K-1] + A[i-1]
  if prev < curr:
    print("Yes")
  else:
    print("No")
  prev = curr
### BUGGY CODE ###

N = int(input())
d = list(map(int,input().split()))
d.sort()
var = 0
y = d[N//2] - d[(N//2)-1]
k = d[(N//2)-1]
for j in range(y):
  k = k+1
  m = len([i for i in d if i < k])
  if m*2 == N:
    var = var + 1
print(var)

### FIXED CODE ###

N = int(input())
d = list(map(int,input().split()))
d.sort()
y = d[N//2] - d[(N//2)-1]
print(y)
### BUGGY CODE ###

N = int(input())
n = 1000000007
p = 1
for i in range(1, N + 1):
    p *= i
print(p % n)


### FIXED CODE ###

N = int(input())
n = 1000000007
p = 1
for i in range(1, N + 1):
    p *= i
    p %= n
print(p)
### BUGGY CODE ###

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

m = [0] * n
for i in range(n-k+1):
  m[i] = sum(p[i:i+k])
print((max(m) + k)/2)

### FIXED CODE ###

import itertools

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

pa = list(itertools.accumulate([0] + p))

m = 0
for i in range(n-k+1):
  s = pa[i+k] - pa[i]
  if s > m:
    m = s
print((m+k)/2)
### BUGGY CODE ###

import numpy as np


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

    MAX = 10 ** 5 + 10
    k = [0] * MAX
    # v = [0] * MAX

    for a in A:
        k[a] += 1

    num = np.arange(MAX)

    arr_k = np.array(k)

    for i in range(Q):
        b, c = map(int, input().split())
        if arr_k[b] > 0:
            arr_k[c] += arr_k[b]
            arr_k[b] = 0
        ans = np.sum(arr_k * num)
        print(ans)

    # print(k[:10])

    # for i in range(Q):
    #     ans = 0
    #     b, c = map(int, input().split())
    #     if k[b] > 0:
    #         k[c] += k[b]
    #         k[b] = 0
    #     for i in range(MAX):
    #         ans += i * k[i]
    #     print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter
import sys

input = sys.stdin.readline


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

    d = Counter(A)
    # print(d)
    ans = sum(A)

    for i in range(Q):
        b, c = map(int, input().split())
        if d[b] != 0:
            ans -= d[b] * b
            ans -= d[c] * c
            d[c] += d[b]
            d[b] = 0
            ans += d[c] * c

        print(ans)


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

S = str(input())
T = str(input())
alp = "abcdefghijklmnopqrstuvwxyz"
for i in range(0,len(S)):
  alp.replace(S[i],"")
  if S[i] != T[i]:
    S = S.translate(str.maketrans({S[i]:T[i], T[i]:S[i]}))
  else:
    pass
  if S == T:
    print("Yes")
    exit()
  if alp == "":
    break
print("No")

### FIXED CODE ###

S = str(input())
T = str(input())
alp = "abcdefghijklmnopqrstuvwxyz"
for i in range(0,min(len(S),len(alp)*2)):
  if S[i] != T[i]:
    S = S.translate(str.maketrans({S[i]:T[i], T[i]:S[i]}))
  else:
    pass
  if S == T:
    print("Yes")
    exit()
print("No")
### BUGGY CODE ###

N=int(input())
listN=[]
i=0
while N!=0:
  listN.append(N%10)
  N=N//10
  i+=1
k=0
for j in range(i):
  k+=listN[j]
  k=k%9
  
if k%9==0:
  print ('Yes')
else:
  print ('No')

### FIXED CODE ###

N=int(input())
if N%9==0:
  print ('Yes')
else:
  print ('No')
### BUGGY CODE ###

S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1])

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])


### FIXED CODE ###

S = input()
S = S[::-1]
#print(S)

mod = 10**9+7

tblpow = [1]
for i in range(1,len(S)+1):
	tblpow.append(10*tblpow[i-1]%13)

dp = [0]*13
dp[0] = 1
for i in range(len(S)-1,-1,-1):
	ch = int(S[i]) if S[i]!='?' else -1
	temp = [0]*13
	for d in range(10):
		if ch!=-1 and ch!=d:
			continue
		for m in range(13):
			temp[(d*tblpow[i]+m)%13] += dp[m]
	for m in range(13):
		temp[m] %= mod
	dp = temp
print(dp[5])
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse.csgraph import floyd_warshall
n=int(input())
g=[[float('inf') for i in range(n)]for j in range(n)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
q,k=map(int,input().split())
k-=1
cost=dijkstra(g,unweighted=False,directed=False)
z=[]
for i in range(q):
    a,b=map(int,input().split())
    z.append((a-1,b-1))
for i,j in z:
    print(int(cost[i][k]+cost[k][j]))


### FIXED CODE ###

n=int(input())
ro=[{}for i in range(n)]
dis=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    ro[a-1][b-1]=c
    ro[b-1][a-1]=c
q,k=map(int,input().split())
dis[k-1]=0
stack=[k-1]
while stack:
    s=stack.pop()
    for i,j in ro[s].items():
        if dis[i] == -1:
            dis[i]=dis[s]+j
            stack.append(i)
for i in range(q):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    print(dis[x]+dis[y])
### BUGGY CODE ###

def solve():
    h, k = read()
    result = think(h, k)
    write(result)


def read():
    n, k = read_int(2)
    return read_int(n), k


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(h, k):
    cache = preprocess(h, k)
    cost = [0 for x in range(len(h))]
    # element of h <= 10 ** 4, elements <= 10 ** 5, +1 in case
    initial_value_of_cost = 10 ** (4 + 5) + 1
    for dst in range(1, len(h)):
        minimum_cost = initial_value_of_cost
        for src in range(max(0, dst - k), dst):
            minimum_cost = min(minimum_cost, cost[src] + cache[create_key_for_cache(src, dst)])
        cost[dst] = minimum_cost
    return cost[len(h) - 1]


def preprocess(h, k):
    cache = {}
    for src in range(len(h) - 1):
        for dst in range(src + 1, min(len(h), src + k + 1)):
            cost = abs(h[src] - h[dst])
            key = create_key_for_cache(src, dst)
            cache[key] = cost
    return cache

            
def create_key_for_cache(src, dst):
    return '{0:d},{1:d}'.format(src, dst)


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    h, k = read()
    result = think(h, k)
    write(result)


def read():
    n, k = read_int(2)
    return read_int(n), k


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(h, k):
    cost = [0 for x in range(len(h))]
    for dst in range(1, len(h)):
        start_point = max(0, dst - k)
        cost[dst] = min([cost[src] + abs(h[src] - h[dst]) for src in range(start_point, dst)])
    return cost[len(h) - 1]


def write(result):
    print(result)


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

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

answer = [0] * kn[1]

for j in range(kn[1]):
    for i in range(kn[1]-1):
        if i+j != kn[1]-1:
            answer[j] = answer[j] + A[(i+j+1)%3] - A[(i+j)%3]
        else:
            answer[j] = answer[j] + kn[0] - A[-1] + A[0]
print(min(answer))

### FIXED CODE ###

k,n = map(int,input().split())
a = list(map(int,input().split()))
dis = [0]*n
for i in range(n):
    if i == 0:
        dis[i] = a[-1] - a[0]
    else:
        dis[i] = k - a[i] + a[i-1]
print(min(dis))
### BUGGY CODE ###

N = int(input())
C = 0
while N > 0:
    C += N % 10
    N = N // 10
if C % 9 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = input()
C = 0
for s in N:
    C += int(s)
if C % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort()
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良いわけではない，不必要な分も考えなければならない             
    def ch(x):
        if a[x]>=K:
            return True
        else:
            #使い回す，i番目まででjが作れるか
            dp=[False]*K
            dp[0]=True
            for i in range(N):
                if i==x:
                    continue
                else:
                    for j in range(K-1,a[i]-1,-1):
                        dp[j]|=dp[j-a[i]]
                    
                            
            #K未満K-a[x]以上が作れれば良い    
            for j in range(K-a[x],K):
                if  dp[j]:
                    return True
            return False
                
            
            
        return False
    
                        
    ng=-1
    ok=N
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ng+1)
    
    
   
    
            
    
    
    

main()


### FIXED CODE ###

def main():
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort()
    for i in range(N):#K以上ならば必要
        if a[i]>=K:
            a=a[:i]
            break
    N=len(a)
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良いわけではない，不必要な分も考えなければならない             
    def ch(x):
        
        #使い回す，i番目まででjが作れるか
        dp=[0]*K
        dp[0]=1
        for i in range(N):
            if i==x:
                continue
            else:
                for j in range(K-1,a[i]-1,-1):
                    dp[j]|=dp[j-a[i]]
                
                        
        #K未満K-a[x]以上が作れれば良い    
        for j in range(K-a[x],K):
            if  dp[j]:
                return True
        return False
            
    
                        
    ng=-1
    ok=N
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ng+1)
    
    
 
    

main()
### BUGGY CODE ###

num = int(input())
numbers = list(map(int,input().split()))
sum = 1
for i in range(num):
  sum *=numbers[i]
if (sum>(10**18)):
  print (-1)
else :
  print (sum)

### FIXED CODE ###

num = int(input())
numbers = list(map(int,input().split()))
sum = 1
for i in range(num):
  sum *=numbers[i]
  if (sum>(10**18)):
    sum = -1
    break
if 0 in numbers:
  sum = 0
print (sum)