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

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
mid = []
for i in range(m):
  if ab[i][0] == 1:
    mid.append(ab[i][1])
  elif ab[i][1] == 1:
    mid.append(ab[i][0])

for j in range(m):
  if ab[j][0] in mid and ab[j][1] == n:
    print('POSSIBLE')
    exit()
  elif ab[j][1] in mid and ab[j][0] == n:
    print('POSSIBLE')
    exit()

print('IMPOSSIBLE')

### FIXED CODE ###

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
ab.sort()
mid = []
cand = []
for i in range(m):
  if ab[i][0] == 1:
    mid.append(ab[i][1])
  elif ab[i][0] == n:
    cand.append(ab[i][1])
  elif ab[i][1] == n:
    cand.append(ab[i][0])    

if len(set(mid) & set(cand)) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

a, b = map(int, input().split())
ans = 1

for i in range(a, b + 1):
    ans = ans * i

if ans > 0:
    print("Positive")
elif ans == 0:
    print("Zero")
elif ans < 0:
    print("Negative")

### FIXED CODE ###

a, b = map(int, input().split())
ans = 1

if a > 0 and b > 0:
    print("Positive")
elif a == 0:
    print("Zero")
elif a < 0 and b > 0:
    print("Zero")
elif b == 0:
    print("Zero")
elif a < 0 and b < 0:
    diff = b - a
    if diff % 2 == 0:
        print("Negative")
    elif diff % 2 != 0:
        print("Positive")
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin



def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = {}

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)

  for d in Dn[:-1]:
    ans[d] = -1

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])
    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

N = int(input())
An = list(map(int,input().split()))
mult =1
for i in An:
  mult *= i

if mult >10**18:
  print(-1)
else:
  print(mult)

### FIXED CODE ###

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

if 0 in An:
  print(0)

else:
  mult =1
  for i in An:
    mult *= i
    if mult > 10**18:
      print(-1)
      break

  else:
    print(mult)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)


from collections import deque
n, m = map(int, input().split())
g = [[] for i in range(n)]
deg = [0]*n
deg2 = [0]*n
atode = []
for i in range(m):
    s, t = map(int, input().split())
    g[s-1].append(t-1)
    deg[t-1] += 1
    deg2[s-1] += 1
    atode.append((s-1,t-1))

ans = list(v for v in range(n) if deg[v]==0)
deq = deque(ans)
used = [0]*n

while deq:
    v = deq.popleft()
    for t in g[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)
# ansがトポロジカル順番

# convert
c = {j:i for i,j in enumerate(ans)}

# まず、O(N)で期待値を求める
e = [-1]*n
#print(g)
def rec(cur):
    if e[cur] != -1:
        return e[cur]
    res = 0
    cnt = 0
    for to in g[cur]:
        res += rec(to)+1
        cnt += 1
    # 0のとき→end
    if cnt:
        res /= cnt
    e[cur] = res
    return e[cur]

rec(0)
ee = [-1]*n
def rec2(cur, s,t):
    # 計算を飛ばせる時
    if c[cur] > c[s]:
        return e[cur]
    # 計算済みのとき
    if ee[cur] != -1:
        return ee[cur]
    # 計算する
    res = 0
    cnt = 0
    for to in g[cur]:
        if cur==s and to ==t:
            continue
        res += rec2(to,s,t)+1
        cnt += 1
    if cnt:
        res /= cnt
    ee[cur] = res
    return ee[cur]

ret = e[0]

use = [[-1, -1] for i in range(n)]
for s,t in atode:
    if deg2[s] < 2:
        continue
    if use[s][1] < e[t]:
        use[s][0] = t
        use[s][1] = e[t]

for s, (t,cost) in enumerate(use):
    if s == -1:
        continue
    ee = [-1]*n
    rec2(0,s,t)
    ret = min(ret, ee[0])
print(ret)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def main():
    n, m = map(int, input().split())
    g = [[] for i in range(n)]
    deg2 = [0]*n
    atode = []
    for i in range(m):
        s, t = map(int, input().split())
        g[s-1].append(t-1)
        deg2[s-1] += 1
        atode.append((s-1,t-1))

    ee = [-1]*n
    def rec2(cur, s,t):
        if ee[cur] != -1:
            return ee[cur]
        res = 0
        cnt = 0
        for to in g[cur]:
            if cur==s and to ==t:
                continue
            res += rec2(to,s,t)+1
            cnt += 1
        if cnt:
            res /= cnt
        ee[cur] = res
        return ee[cur]

    rec2(0,-1,-1)
    ret = ee[0]

    use = [[-1, -1] for i in range(n)]
    for s,t in atode:
        if deg2[s] < 2:
            continue
        if use[s][1] < ee[t]:
            use[s][0] = t
            use[s][1] = ee[t]

    for s, (t,cost) in enumerate(use):
        if s == -1:
            continue
        ee = [-1]*n
        rec2(0,s,t)
        ret = min(ret, ee[0])
    print(ret)

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

import sys
input = sys.stdin.readline
n,k = map(int,input().split())

A = list(map(int,input().split()))
sum = 0
import collections

c = collections.Counter(A)
c = c.most_common()
while len(c) > k:
    sum += c[-1][1]
    c = c[:-1]
print(sum)

### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline
n,k = map(int,input().split())

A = list(map(int,input().split()))
sum = 0
c = collections.Counter(A)
c = c.most_common()
if len(c) > k:
  a = len(c)-k
  c = c[-a:]
  for i in range(a):
    sum += c[i][1]
  print(sum)
else:
  print(0)
### BUGGY CODE ###

import math

N = 10
ARR = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

N = 10
ARR = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

# N = 3
# ARR = [1, 2, 3]

# N = 5
# ARR = [3, 6, 8, 9, 10]

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


def calculate(n, arr):
    if max(arr) == 0:
        mathNum = 1
    else:
        mathNum = math.ceil(math.log(max(arr), 2)) + 1
    result = 0
    for i in range(mathNum):

        oneSum = 0
        zeroSum = 0

        for j in range(n):
            if ((arr[j] >> i) & 1) == 0:
                zeroSum += 1
            else:
                oneSum += 1

        result += (2 ** i) * (zeroSum * oneSum)

    print(result % (10**9 + 7))


calculate(N, ARR)


### FIXED CODE ###

import math
import numpy as np

N = 10
ARR = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

N = 10
ARR = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]


# N = 3
# ARR = [1, 2, 3]

# N = 5
# ARR = [3, 6, 8, 9, 10]

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


def calculate(n, arr):
    if max(arr) == 0:
        mathNum = 1
    else:
        mathNum = math.ceil(math.log(max(arr), 2))

    oneArray =  [0] * mathNum
    zeroArray = [0] * mathNum

    result = 0
    arr = np.array(arr)
    for i in range(mathNum):
        s = (arr >> i) & 1

        oneCount = np.count_nonzero(s)
        zeroCount = n - oneCount
        oneArray[i] = oneCount
        zeroArray[i] = zeroCount

    for i in range(mathNum):
        result += (2 ** i) * (oneArray[i] * zeroArray[i])

    print(result % (10 ** 9 + 7))


calculate(N, ARR)
### BUGGY CODE ###

import cmath
pi = cmath.pi
exp = cmath.exp

import sys
readline = sys.stdin.readline
write = sys.stdout.write

def make_exp_t(N, base):
    exp_t = {0: 1}
    temp = N
    while temp:
        exp_t[temp] = exp(base / temp)
        temp >>= 1
    return exp_t

def fft_dfs(f, s, N, st, exp_t):
    if N==2:
        a = f[s]; b = f[s+st]
        return [a+b, a-b]
    N2 = N//2; st2 = st*2
    F0 = fft_dfs(f, s   , N2, st2, exp_t)
    F1 = fft_dfs(f, s+st, N2, st2, exp_t)
    w = exp_t[N]; wk = 1.0
    for k in range(N2):
        U = F0[k]; V = wk * F1[k]
        F0[k] = U + V
        F1[k] = U - V
        wk *= w
    F0.extend(F1)
    return F0

def fft(f, N):
    if N==1:
        return f
    return fft_dfs(f, 0, N, 1, fft_exp_t)

def ifft(F, N):
    if N==1:
        return F
    f = fft_dfs(F, 0, N, 1, ifft_exp_t)
    for i in range(N):
        f[i] /= N
    return f

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

l = 10**5+1
L = 2**(2*l-1).bit_length()

power = list(map(int,input().split()))
count = [0.0 for _ in range(l)]

for p in power:
    count[p] += 1

fft_exp_t = make_exp_t(L, -2j*pi)
ifft_exp_t = make_exp_t(L, 2j*pi)

count.extend([0]*(L-l))

C = fft(count, L)

CC =[C[i]*C[i] for i in range(L)]

cc = ifft(CC,L)

shake = 0
ans = 0

for i in reversed(range(len(cc))):
    if shake+int(cc[i].real+0.5)<=M:
        ans += i*int(cc[i].real+0.5)
        shake += int(cc[i].real+0.5)
    else:
        ans += i*(M-shake)
        break
        
print(ans)

### FIXED CODE ###

import cmath
pi = cmath.pi
exp = cmath.exp

import sys
readline = sys.stdin.readline
write = sys.stdout.write

def make_exp_t(N, base):
    exp_t = {0: 1}
    temp = N
    while temp:
        exp_t[temp] = exp(base / temp)
        temp >>= 1
    return exp_t

def fft_dfs(f, s, N, st, exp_t):
    if N==2:
        a = f[s]; b = f[s+st]
        return [a+b, a-b]
    N2 = N//2; st2 = st*2
    F0 = fft_dfs(f, s   , N2, st2, exp_t)
    F1 = fft_dfs(f, s+st, N2, st2, exp_t)
    w = exp_t[N]; wk = 1.0
    for k in range(N2):
        U = F0[k]; V = wk * F1[k]
        F0[k] = U + V
        F1[k] = U - V
        wk *= w
    F0.extend(F1)
    return F0

def fft(f, N):
    if N==1:
        return f
    return fft_dfs(f, 0, N, 1, fft_exp_t)

def ifft(F, N):
    if N==1:
        return F
    f = fft_dfs(F, 0, N, 1, ifft_exp_t)
    for i in range(N):
        f[i] /= N
    return f

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

l = 10**5+1
L = 2**(2*l-1).bit_length()

power = list(map(int,input().split()))
count = [0.0 for _ in range(l)]

for p in power:
    count[p] += 1

fft_exp_t = make_exp_t(L, -2j*pi)
ifft_exp_t = make_exp_t(L, 2j*pi)

count.extend([0]*(L-l))

C = fft(count, L)

CC =[C[i]*C[i] for i in range(L)]

cc = ifft(CC,L)

shake = 0
ans = 0

for i in reversed(range(len(cc))):
    if shake+int(cc[i].real+0.5)<=M:
        ans += i*int(cc[i].real+0.5)
        shake += int(cc[i].real+0.5)
    else:
        ans += i*(M-shake)
        break
        
print(ans)
### BUGGY CODE ###

from collections import deque

n,m=map(int,input().split())
a=list(map(int,input().split()))
a=deque(a)
for i in range(m):
  b,c=map(int,input().split())
  a.extend([c for _ in range(b)])
a=list(a)
#print(a)
a.sort(reverse=1)
a=a[:n]





print(sum(a))
#print(a)

### FIXED CODE ###

from collections import deque

n,m=map(int,input().split())
a=deque(map(int,input().split()))
bc=[list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1])
bc=bc[::-1]
l=0
for b,c in bc:
  if l>n:
    break
  else:
    d=[c]*b
    a.extend(d)
    l+=b


a=list(a)
#print(a)
a.sort(reverse=1)
a=a[:n]





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

from sys import stdin
import bisect

N = int(stdin.readline().rstrip())
A = [int(stdin.readline().rstrip()) for _ in range(N)]

colors = [10 ** 10]
for i in range(N):
    bi = bisect.bisect_left(colors, A[i])
    bir = bisect.bisect_right(colors, A[i])
    if bir == len(A):
        colors[len(A) - 1] = A[i]
    elif bi == 0:
        bisect.insort_left(colors, A[i])
    else:
        colors[bi - 1] = A[i]

print(len(colors) - 1)


### FIXED CODE ###

from sys import stdin
import bisect
from collections import deque

N = int(stdin.readline().rstrip())
A = [int(stdin.readline().rstrip()) for _ in range(N)]

colors = deque([10 ** 10])
for i in range(N):
    bi = bisect.bisect_left(colors, A[i])
    bir = bisect.bisect_right(colors, A[i])
    if bir == len(A):
        colors[len(A) - 1] = A[i]
    elif bi == 0:
        colors.appendleft(A[i])
    else:
        colors[bi - 1] = A[i]

print(len(colors) - 1)
### BUGGY CODE ###

s = input()
K = int(input())
ans_lis = []
s_length = len(s)
lis = [[] for i in range(26)]

for i in range(s_length):
    lis[ord(s[i]) - ord('a')].append(i)


for i in range(26):
    for j in lis[i]:
        k = j
        while k <= K + 10000:
            ans_lis.append(s[j:k + 1])
            k += 1
    ans_lis = sorted(list(set(ans_lis)))
    if len(ans_lis) >= K:
        print(ans_lis[K - 1])
        exit()


### FIXED CODE ###

s = input()
K = int(input())
ans_lis = []
s_length = len(s)
lis = [[] for i in range(26)]

for i in range(s_length):
    lis[ord(s[i]) - ord('a')].append(i)


for i in range(26):
    k = 1
    while k <= K:
        for j in lis[i]:
            ans_lis.append(s[j:j + k])
        k += 1
        ans_lis = sorted(list(set(ans_lis)))
    if len(ans_lis) >= K:
        print(ans_lis[K - 1])
        exit()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range(N):
  ans *= A[i]
if ans > 10**18:
  print(-1)
else:
  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 ###

# coding: utf-8

N = int(input())
#S = [[]]
S = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    chars = input()
    for j in range(N):
        S[i][j] = chars[j]
    #S.append(input().split())

S2 = [[0 for i in range(N)] for j in range(N)]
# for i in range(len(S)):
#     for j in range(len(S[i])):
#         S2[i][j] = S[i][j]

# 対角行列の対象成分だけ見れば良い
ans = 0
for A in range(N):
    for B in range(N):
        okFlg = True
        for i in range(N):
            for j in range(N):
                ii = i + A
                jj = j + B
                if ii >= N:
                    ii -= N
                if jj >= N:
                    jj -= N

                S2[ii][jj] = S[i][j]
            #s_row = S[ii][jj]
            #s_col = S[jj][ii]

        for i in range(N):
            for j in range(N):
                if S2[i][j] != S2[j][i]:
                    okFlg = False
                    break
        if okFlg == True:
            ans += 1

print(ans)

### FIXED CODE ###

# coding: utf-8
import numpy as np

# AとB(行と列の移動量)を入れ替えた場合も対称になりたつ。
N = int(input())
# numpyを使うため、文字を文字コードの数字に置き換えている(ord関数)
S = [list(map( ord, list(input()) )) for _ in range(N)]
Sarr = np.array(S)
# 配列をひとまとめにしてタイル状に複製して配置
# 行, 列のアクセスインデックスが行、列の大きさを飛び越えると
# それぞれ先頭にインデックスを戻す必要があるところを行列を拡張して対応する
Sext = np.tile(Sarr, [2,1])[:-1,:]
# 拡張は行方向だけで良さそう
#Sext = np.tile(Sarr, [2,2])[:-1,:-1]

cnt = 0
for i in range(N):
    # 行について1つずつずらしたスタート位置で配列を取得し、
    # 転置したものと等しくなっていれば、良い配列
    # 行と列の移動量の差(A-B)が同一のときは対角線成分に対して
    # 線対称を判定する要素の組み合わせが変わらない。
    # そのため、列は探索せずに、N倍すればよい
    ar = Sext[i:i+N, 0:N]
    cnt += N * (ar == ar.T).all()

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

def simulate(n):
    if n==-1: return 0
    if n==N: return 2
    
    for i in range(Q):
        if TD[i][0]==s[n]:
            if TD[i][1]=="R": n+=1
            if TD[i][1]=="L": n-=1

        if n<0 : return 0
        elif n>=N: return 2 
    return 1

N, Q = map(int, input().split())
s = input()
TD = [input().split() for i in range(Q)]
memo=[-1]*(N+2)


low = 0
high =N-1
# t は中央番目の数
t =int((low+high)/2) 

# 探索の下限のlowが上限のhighになるまで探索
# lowがhighに達すると数は見つからなかったということ
while (1):
    if memo[t]==-1: memo[t]=simulate(t)
    if memo[t+1]==-1: memo[t+1]=simulate(t+1)
    
    if memo[t] in [0,1] and memo[t+1]==2:
        break
    elif memo[t] in [0,1]:
        low = t+1
    elif memo[t]==2:
        high = t-1
    t = int((low + high) / 2)


R=t

low = 0
high =N-1
# t は中央番目の数
t =int((low+high)/2) 

while (1):
    if memo[t]==-1: memo[t]=simulate(t)
    if memo[t-1]==-1: memo[t-1]=simulate(t-1)
    
    if memo[t-1]==0 and memo[t] in [1,2]:
        break
    elif memo[t]==0:
        low = t+1
    elif memo[t] in [1,2]:
        high = t-1
    t = int((low + high) / 2)

L=t

print(R-L+1)

### FIXED CODE ###

N,Q=map(int,input().split())
s="0"+input()+"0"
queri=[list(input().split()) for i in range(Q)]

L,R=0,N+1
for i in range(Q-1,-1,-1):
    t,d=queri[i]
    if t==s[L] and d=="R":
        L-=1
    elif t==s[L+1] and d=="L":
        L+=1
    if t==s[R] and d=="L":
        R+=1
    elif t==s[R-1] and d=="R":
        R-=1

print(R-L-1)
### BUGGY CODE ###

from scipy.spatial import ConvexHull
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
tmp = set()
dots = []
for _ in range(N):
    x, y = map(int, input().split())
    tmp.add((x, y))
    dots.append([x, y])

# 直線状か判定
isline = True
x1, y1 = dots[0]
x2, y2 = dots[1]
for i in range(2, N):
    x3, y3 = dots[i]
    isline &= (y3 - y1) * (x2 - x1) == (y2 - y1) * (x3 - x1)

if not isline:
    hull = ConvexHull(dots).points + 0.1

    dots = np.array(hull, dtype=np.int64).tolist()
    M = len(dots)

    ans = 0
    for i in range(M-1):
        xi, yi = dots[i]
        for j in range(i + 1, M):
            xj, yj = dots[j]
            ans = max(ans, abs(xi - xj) + abs(yi - yj))
    print(ans)
else:
    dots.sort()
    xi, yi = dots[0]
    xj, yj = dots[-1]
    print(abs(xi - xj) + abs(yi - yj))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
inf = 10**18

N = int(input())
xmax = -inf
xmin = inf
ymax = -inf
ymin = inf
for _ in range(N):
    a, b = map(int, input().split())
    x = a + b
    y = a - b
    xmax = max(xmax, x)
    xmin = min(xmin, x)
    ymax = max(ymax, y)
    ymin = min(ymin, y)

print(max(xmax-xmin, ymax-ymin))
### BUGGY CODE ###

def main():
    n = int(input())
    ans = 0

    e = 1
    for fac in (2, *(x * 2 + 3 for x in range(pow(10, 12)))):
        while n % (div := pow(fac, e)) == 0:
            n //= div
            ans += 1
            e += 1

        while n % fac == 0:
            n //= fac

        if fac * fac > n:
            break
        e = 1

    if n != 1:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
from itertools import accumulate


def prime_factorize(n):
    """素因数分解し，ユニークな素因数のsetを返す。"""
    ans = []
    ans_add = ans.append
    while n % 2 == 0:
        ans_add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            ans_add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        ans_add(n)
    return ans


def main():
    n = int(input())
    primes = prime_factorize(n)
    acc = tuple(accumulate(range(1, 42)))
    counted = Counter(primes)
    ans = 0

    for c in counted.values():
        for i, x in enumerate(acc):
            if c >= x:
                tmp = i + 1
            else:
                break
        ans += tmp

    print(ans)


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

def popcount(n):
    return bin(n).count('1')

def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)
    pcount_X = popcount(X_int)

    for i,bit in enumerate(X):
        Xi = X_int + 2**(N-i-1) * (-1)**int(bit)

        pcount_Xi = pcount_X + (-1)**int(bit)

        n = Xi
        pcount_n = pcount_Xi
        ans = 0
        while n > 0:
            ans += 1
            n %= pcount_n
            pcount_n = popcount(n)
        print(ans)

main()

### FIXED CODE ###

def popcount(n):
    return bin(n).count('1')


def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)

    pcount_X = popcount(X_int)

    pcount_X_pls1 = pcount_X + 1
    pcount_X_mns1 = pcount_X - 1
    
    X_mod_pcount_X_pls1 = X_int % pcount_X_pls1
    if pcount_X_mns1 != 0:
        X_mod_pcount_X_mns1 = X_int % pcount_X_mns1

    for i,bit in enumerate(X):
        bit = int(bit)
        if bit == 0:
            n = (X_mod_pcount_X_pls1 + pow(2, N-i-1, pcount_X_pls1)) % pcount_X_pls1
        else:
            if pcount_X_mns1 == 0:
                print(0)
                continue
            n = (X_mod_pcount_X_mns1 - pow(2, N-i-1, pcount_X_mns1)) % pcount_X_mns1

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()
### BUGGY CODE ###

# M: 鍵の数
# N: 宝箱の数(制限値になる)
# openable: 開けられる宝箱のリスト
# price: 鍵の価格

def power(n):
    if n == 0:
        return [[]]
    else:
        l = []
        for i in power(n-1):
            k = i + [n]
            l.append(k)
        return power(n-1) + l

def abc142e(M, N, price, openable):
    # dp initialize
    inf = float("inf")
    dp = [[inf for j in range((2**N)+1)] for i in range(M+10)]
    for i in range(M+10):
        dp[i][0] = 0
    closed_boxes = power(N)
    # dp
    for i in range(M):
        if openable[i] not in closed_boxes:
            dp[i][j] = inf
        else:
            for j in range(len(closed_boxes)):
                l = list(set(closed_boxes[j])-set(openable[i]))
                l.sort()
                dp[i+1][j] = min(dp[i][closed_boxes.index(l)]+price[i], dp[i][j])
    if dp[M][2**N-1] == inf: return -1
    else: return dp[M][2**N-1]

if __name__ == "__main__":
    N,M = map(int, input().split())
    price = []
    openable = []
    for i in range(M):
        a,b = map(int, input().split())
        c = [i for i in map(int, input().split())]
        price.append(a)
        openable.append(c)

    print(abc142e(M, N, price, openable))



### FIXED CODE ###

def main():
    N,M = map(int, input().split())
    inf = 10**9
    p = 2**N
    dp = [inf] * p
    dp[0] = 0
    
    for i in range(M):
        a,b = map(int, input().split())
        c = sum([2**(int(j)-1) for j in list(input().split())])
        for k in range(p):
            if dp[k|c] > dp[k] + a:
                dp[k|c] = dp[k] + a
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])

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

import sys

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

def solve():
  ret = 1
  for x in A:
    ret *= x
  if ret > 1e18:
      ret += 1
  if ret > 1e18:
    ret = -1
  return ret

print(solve())

### FIXED CODE ###

import sys

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

U = 10**18
ret = 1

for x in A:
  ret *= x
  if ret > U:
    ret = U+1
    
if ret > U:
  ret = -1

print(ret)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

#K = int(input())
#S = input()

##一次元配列の初期化
#a=[0]*5
#[i for i in range(100) if i%2==1] #奇数のみ
##二次元配列の初期化
#mod = np.array([[-1 for i in range(N)] for i in range(N)])
#A = list(set(A))
A = sorted(A)#わるほう

kouho = list(A.copy())#わられるほう
target = list(set(A))
#print(A)

for i in range(1,len(kouho)):
    if (kouho[max(0,i-1)]==kouho[i]):
        if kouho[i] in target:
            target.remove(kouho[i])
            
kouho = sorted(list(target.copy()))

for i in range(len(A)):
    for j in range(0, len(target)):
        if target[j] <= A[i]:
            continue
        elif  target[j] in kouho:
            if target[j] % A[i] == 0:
                #print(target[j], A[i])
                kouho.remove(target[j])
    target = list(kouho.copy())
        
print(len(target))

### FIXED CODE ###

#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    if work[A[i]]<=1:
        maxN = int(maxA/A[i])
        for n in range(1,maxN+1):
            buf = A[i]*n
            #remove_list.append(buf)
            work[buf]+=1
                #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))