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

N,W=map(int,input().split())
weight=[0]*N
value=[0]*N
for i in range(N):
    weight[i],value[i]=map(int,input().split())
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if(j>=weight[i]):
            dp[i+1][j]=max(dp[i][j-weight[i]]+value[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[N][W])

### FIXED CODE ###

N,W=map(int,input().split())
weight=[0]*N
value=[0]*N
for i in range(N):
    weight[i],value[i]=map(int,input().split())
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if(j>=weight[i]):
            dp[i+1][j]=max(dp[i][j-weight[i]]+value[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[N][W])
### BUGGY CODE ###

def list_difference(list1, list2):
    result = list1.copy()
    for value in list2:
        if value in result:
            result.remove(value)
    return result

n=int(input())
l1=list(map(int,input().split()))
m=int(input())
l2=list(map(int,input().split()))

x=list_difference(l2,l1)

if x==[]: print('YES')
else: print('NO')

### FIXED CODE ###

from collections import Counter

n = int(input())
l1 = list(map(int,input().split()))
l1_cnt = Counter(l1) 

m = int(input())
l2 = list(map(int,input().split()))
l2_cnt = Counter(l2) 
l2_set=set(l2)

for i in l2_set:
    if l2_cnt[i]<=l1_cnt[i]:
        continue
    else:
        print('NO')
        break
else:
    print('YES')
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)

n = int(input())
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in graph.items():
    if len(v) > _max:
        _max = len(v)
        _max_node = k
colors = [[0 for i in range(n)] for j in range(n)]
que = deque()
color_dict = {i : [] for i in range(n)}
cur = _max_node
while True:
    cnt = 1
    for _next in graph[cur]:
        if colors[cur][_next] == 0:
            if _next not in que:
                que.append(_next)
            candidate = color_dict[_next] + color_dict[cur]
            while cnt in candidate:
                cnt = cnt + 1 if cnt + 1 <= _max else 1
            colors[cur][_next] = cnt
            colors[_next][cur] = cnt
            color_dict[cur].append(cnt)
            color_dict[_next].append(cnt)
            cnt += 1
    if len(que) == 0:
        break
    cur = que.popleft()
print(_max)
for a, b in ls:
    print(colors[a][b])

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)

n = int(input())
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in graph.items():
    if len(v) > _max:
        _max = len(v)
        _max_node = k

parent = [_max_node] * (n)
order = []
stack = [_max_node]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

colors = [-1 for i in range(n)]
for i in order:
    c = 1
    for _next in graph[i]:
        if _next == parent[i]:
            continue
        if c == colors[i]:
            c += 1
        colors[_next] = c
        c += 1
print(_max)
for a, b in ls:
    if parent[a] == b:
        print(colors[a])
    else:
        print(colors[b])
### BUGGY CODE ###

import math

k = int(input())
A = 0

def gcd(a,b,c):
    d = math.gcd(a,b)
    e = math.gcd(d,c)
    return e

for a in range(k):
    for b in range(k):
        for c in range(k):
            y = gcd(a+1,b+1,c+1)
            A += y

print(A)





### FIXED CODE ###

import math

k = int(input())
A = 0

for a in range(1,k+1):
    for b in range(1,k+1):
        p = math.gcd(a,b)
        for c in range(1,k+1):
            y = math.gcd(p,c)
            A += y

print(A)
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
ab = []
edge = [[] for _ in range(n)]
mat = [[1000] * n for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            mat[i][j] = 1
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
                ab.append((i, j))
for i in range(n):
    mat[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

ans = 0
dq = deque()
dist = [-1] * n
dq.append((i, 0))
ok = True
while dq:
    v, d = dq.popleft()
    if dist[v] == -1:
        dist[v] = d
    elif dist[v] != d:
        ok = False
        break
    for item in edge[v]:
        if dist[item] == -1:
            dq.append((item, d+1))
if ok:
    ans = 0
    for line in mat:
        ans = max(ans, max(line))
    print(ans + 1)
else:
    print(-1)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
edge = [[] for _ in range(n)]
mat = [[1000] * n for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            mat[i][j] = 1
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
for i in range(n):
    mat[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

ans = 0
dq = deque()
dist = [-1] * n
dq.append((0, 0))
ok = True
while dq:
    v, d = dq.popleft()
    if dist[v] == d:
        continue
    if dist[v] == -1:
        dist[v] = d
    else:
        ok = False
        break
    for item in edge[v]:
        if dist[item] == -1:
            dq.append((item, d+1))

if ok:
    ans = 0
    for line in mat:
        ans = max(ans, max(line))
    print(ans + 1)
else:
    print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys


def main():
    _ = sys.stdin.readline()
    arr = []
    for line in sys.stdin:
        num = line.rstrip()
        if num in arr:
            arr.remove(num)
        else:
            arr.append(num)
    print(len(arr))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys


def main():
    _ = sys.stdin.readline()
    arr = set()
    for line in sys.stdin:
        num = line.rstrip()
        if num in arr:
            arr.remove(num)
        else:
            arr.add(num)
    print(len(arr))


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

H, N = map(int, input().split())
dp = [ float("inf") for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])

### FIXED CODE ###

H, N = map(int, input().split())
dp = [ 1001001001 for _ in range(H+1)]
dp[0] = 0
for i in range(N):
  A, B = map(int, input().split())
  for j in range(H):
    nj = min(j+A, H)
    dp[nj] = min(dp[nj], dp[j] + B)

print(dp[H])
### BUGGY CODE ###

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

    divisors.sort()
    return divisors

n = int(input())
nl = make_divisors(n)
nl_p = make_divisors(n+1)
nl_m = make_divisors(n-1)
l = sorted(list(set(nl + nl_p+nl_m)))

ans = 0
for i in range(1, len(l)-1):
    p = n
    k = l[i]
    while p > k:
        if p%k == 0:
            p = p//k
        else:
            if (p-1)%k == 0:
                p = 1
                break
            p = p - k
    if p == 1:
        ans += 1
print(ans+1)

### FIXED CODE ###

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

    divisors.sort()
    return divisors

n = int(input())
nl = make_divisors(n)
nl_m = make_divisors(n-1)
l = sorted(list(set(nl + nl_m)))

ans = 0
for i in range(1, len(l)-1):
    p = n
    k = l[i]
    while p%k == 0:
        p = p // k
    if p%k == 1:
        ans += 1
print(ans+1)
### BUGGY CODE ###

n = int(input())
T = []
for _ in range(n-1):
    T += [list(map(int, input().split()))]
T.sort()
P = [0]+[-1]*(n-1)
b = n-1
while b > 0:
    for u, v, w in T:
        pu, pv = P[u-1], P[v-1]
        if (pu >= 0) & (pv < 0):
            P[v-1] = (pu+(w%2))%2
            b -= 1
        if (pv >= 0) & (pu < 0):
            P[u-1] = (pv+(w%2))%2
            b -= 1
for p in P: print(p)

### FIXED CODE ###

n = int(input())
L = [[] for _ in range(n+1)]
R = [[] for _ in range(n+1)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    w %= 2
    L[u] += [[u, v, w]]
    R[v] += [[v, u, w]]
P = [[] for _ in range(2*n+2)]
P[1] += (L[1]+R[1])
L[1] = R[1] = []
for i in range(1, 2*n):
    for _, v, w in P[i]:
        P[i+2-w] += (L[v]+R[v])
        L[v] = R[v] = []
A = []
for p in P[1::2]: A += p
B = set([u for u, *_ in A])
for i in range(1, n+1): print(1 if i in B else 0)
### BUGGY CODE ###

import sys

N = int(input())
S = list(input())

count = sys.maxsize

for i in range(N):
    changeNum = S[:i].count("W") + S[i+1:].count("E")
    count = min(count, changeNum)

print(count)

### FIXED CODE ###

import sys

N = int(input())
S = list(input())

count = sys.maxsize
ans = S[1:].count("E")

for i in range(N-1):
    count = min(ans, count)
    if S[i] == "W":
        if S[i+1] == "W":
            ans += 1
    elif S[i] == "E":
        if S[i+1] == "E":
            ans -= 1

count = min(ans, count)
print(count)
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())

p = 10 ** 9 + 7

from math import factorial
def comb(n, r):
    a = factorial(n)
    b = pow(factorial(n - r), p - 2, p)
    c = pow(factorial(r), p - 2, p)
    return a * b * c % p

def f(i, j):
    return comb(i + j, i)

def g(i, j):
    return f(i + 1, j + 1) - 1

ans = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)

print(ans)

### FIXED CODE ###

def solve():
    r1, c1, r2, c2 = map(int, input().split())
    
    p = 10 ** 9 + 7
    N = r2 + c2 + 2
    fact = [1, 1]
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % p)
    
    def comb(n, r):
        a = fact[n]
        b = pow(fact[r], p - 2, p)
        c = pow(fact[n-r], p - 2, p)
        return a * b * c % p
    
    def f(i, j):
        return comb(i + j, i)
    
    def g(i, j):
        return f(i + 1, j + 1) - 1
    
    ans = g(r2, c2) - g(r2, c1 - 1) - g(r1 - 1, c2) + g(r1 - 1, c1 - 1)
    
    print(ans % p)

solve()
### BUGGY CODE ###

import numpy as np
A,B,Q = list(map(int,input().split())) 
S = [int(input()) for _ in range(A) ]
T = [int(input()) for _ in range(B) ]
x = [int(input()) for _ in range(Q)]
#S = np.array(S)
#T = np.array(T)
for a in x:
    ans1 = 0
    ans2 = 0
    S1 = list(map(lambda x : abs(x-a),S))
    T1 = list(map(lambda x: abs(x-a),T))
    ans1 +=min(T1)
    ans1 += min(map(lambda x:abs(x-T[T1.index(min(T1))]),S))
    ans2+=min(S1)
    ans2+= min(map(lambda x:abs(x-S[S1.index(min(S1))]),T))
    print(min(ans1,ans2))

### FIXED CODE ###

import bisect
A,B,Q = map(int,input().split()) 
INF = 10**18
S = [-INF]+[int(input()) for _ in range(A)]+[INF]
T = [-INF]+[int(input()) for _ in range(B) ]+[INF]
x = [int(input()) for _ in range(Q)]

for a in x:
    ans1 = 0
    ans2 = 0
    b = bisect.bisect_left(S,a)
    c = bisect.bisect_left(T,a)
    res = INF
    for s in [S[b-1],S[b]]:
        for t in [T[c-1],T[c]]:
            d1,d2 = abs(s-a)+abs(s-t),abs(t-a)+abs(s-t)
            res = min(res,d1,d2)
    print(res)
### BUGGY CODE ###

K,S = map(int, input().split())
S1 = 0
S2 = 0
counter = 0
for X in range(min(K,S)+1):
    S1 = S - X
    for Y in range(min(K,S1)+1):
        S2 = S1 - Y
        for Z in range(min(K,S2)+1):
            if X+Y+Z == S:
                counter += 1
                #print(X,Y,Z)
print(counter)

### FIXED CODE ###

K,S = map(int, input().split())
S1 = 0
counter = 0
for X in range(min(K,S)+1):
    S1 = S - X
    for Y in range(min(K,S1)+1):
        Z = S - X - Y
        if (Z >= 0 and Z <= K):
            counter += 1
            #print(X,Y,Z)
print(counter)
### BUGGY CODE ###

n,m=map(int, input().split(' '))
p = list(map(int, input().split(' ')))
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
conlist = [0]*(n+1)
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
stack = []
cnt = 0
for i in range(1,n+1):
    if visited[i] != 1:
        flg = True
        cnt += 1
        stack.append(i)
        connect = []
    while stack:     
        x = stack.pop()
        visited[x] = 1
        connect.append(x)
        for y in graph[x]:
            if visited[y] != 1:
                stack.append(y)
    if flg:
        for i in connect:
            conlist[i] = cnt
        flg = False
ans = 0
for i in range(1,n+1):
    if conlist[p[i-1]] == conlist[i]:
        ans+=1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m=map(int, input().split(' '))
p = list(map(int, input().split(' ')))
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
conlist = [0]*(n+1)
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
stack = []
cnt = 0
append = stack.append
pop = stack.pop
for i in range(1,n+1):
    if visited[i] != 1:
        cnt += 1
        append(i)
    while stack:
        x = pop()
        visited[x] = 1
        conlist[x] = cnt
        for y in graph[x]:
            if visited[y] != 1:
                append(y)
ans = 0
for i in range(1,n+1):
    if conlist[p[i-1]] == conlist[i]:
        ans+=1
print(ans)
### BUGGY CODE ###

import sys
f = sys.stdin

def is_odd(num):
    return num % 2

n,_,_ = map(int,f.readline().split())#_は読み飛ばし
a = list(map(int, f.readline().split()))
q = list(map(int, f.readline().split()))

students = list(range(n))

pos = 0
for ai in a:
    pos += -ai if is_odd(ai) else ai
    pos %= len(students)
    students = students[:pos] + students[pos + 1:]

for qi in q:
    print(1 if qi in students else 0)

### FIXED CODE ###

import sys
f = sys.stdin

def is_odd(num):
    return num % 2

n,_,_ = map(int,f.readline().split())#_は読み飛ばし
a = list(map(int, f.readline().split()))
q = list(map(int, f.readline().split()))

s = list(range(n))

pos = 0
for ai in a:
    pos += -ai if is_odd(ai) else ai
    pos %= len(s)
    s.pop(pos)

for qi in q:
    print(1 if qi in s else 0)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
A_s = list(set(A))
cnt = 0
for i in A_s:
    if A.count(i) % 2 == 1:
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
paper = {}
for i in range(n):
    number = input()
    if number in paper:
        del paper[number]
    else:
        paper[number] = 1
print(len(paper))
### BUGGY CODE ###

A,B,K=map(int,input().split())

for i in range(K):
    if A!=0:
        A-=1
    else:
        B-=1

print("{} {}".format(A,B))

### FIXED CODE ###

A,B,K=map(int,input().split())

if(A>K):
    print("{} {}".format(A-K,B))
else:
    if(B-K+A)>0:
        print("{} {}".format(0,B-K+A))
    else:
        print("0 0")
### BUGGY CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
start = []
sumi= []
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            start.append(i*W+k)

for i in start:
    q.append(i)
    saitan[i] = 0
#print(start)
def bfs(h,w,q,Sumi,Saitan):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0:
        j = q.popleft()
        sumi.append(j)
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if (my*w + mx) in Sumi:
                #print('b')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,sumi,saitan))
#print(saitan)

### FIXED CODE ###

from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
q = deque()
saitan = [1000000]*H*W
for i in range(H):
    for k in range(W):
        if maze[i][k] == '#':
            q.append(i*W+k)
            saitan[i*W+k] = 0
len_q = len(q)

#print(start)
def bfs(h,w,q,Saitan,len_Q):
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while len(q)>0 and len_Q < h * w:
        j = q.popleft()
        y = int(j/w)
        x = j%w
        #print(saitan)
        for k in range(4):
            my = y + dy[k]
            mx = x + dx[k]
            #print(sx,sy,j,x,y,mx,my)
            if not((0 <=my <= h-1) and (0 <= mx <= w-1)):
                #print('q')
                continue
            if saitan[(my*w + mx)] <= saitan[y*w + x] + 1:
                #print('c')
                continue
                
            saitan[(my*w + mx)] = saitan[y*w + x] + 1
            q.append(my*w + mx)
            len_Q += 1
            #Sumi.append(my*w + mx)
    return max(saitan)

print(bfs(H,W,q,saitan,len_q))
#print(saitan)
### BUGGY CODE ###

from itertools import product
N = int(input())

list_N = list(range(1, int((N + 1)**0.5)))

list_xyz = list(product(list_N, repeat=3))

for n in range(1, N+1):
    ans = 0
    for x, y ,z in list_xyz:
        calc = x**2 + y**2 + z ** 2 + x*y + y*z + x * z
        if n == calc:
            ans += 1
    print(ans)

### FIXED CODE ###

from itertools import product
import heapq

N = int(input())

list_N = list(range(1, int((N + 1)**0.5)))

list_xyz = list(product(list_N, repeat=3))

ans_list = [x**2 + y**2 + z ** 2 + x*y + y*z + x * z for x, y ,z in list_xyz]
heapq.heapify(ans_list)
for n in range(1, N+1):
    ans = 0
    while True:
        if len(ans_list) < 1:
            break
        tmp = heapq.heappop(ans_list)
        if tmp == n:
            ans += 1
        elif tmp > n:
            heapq.heappush(ans_list, tmp)
            break
        
    print(ans)
### BUGGY CODE ###

n,m=[int(x) for x in input().split()]
a=[int(x)%m for x in input().split()]

a_ruijou_wa=[0]*(n+1)
for i in range(1,n+1):
    a_ruijou_wa[i]=a_ruijou_wa[i-1]+a[i-1]

ans=0
for sentou in range(n+1):
    for ato in range(sentou):
        if (a_ruijou_wa[sentou] - a_ruijou_wa[ato])%m==0:
            ans+=1
print(ans)

### FIXED CODE ###

n,m=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]

a_ruiseki_wa=[0]
for i in range(n):
    a_ruiseki_wa.append((a_ruiseki_wa[i]+a[i])%m)

from collections import defaultdict
d=defaultdict(int)
for key  in a_ruiseki_wa:
    d[key]+=1

print(sum([x*(x-1)//2 for x in d.values()]))
### BUGGY CODE ###

S=list(input())
N=len(S)

T=[0 for _ in range(N)]

for i in range(N):
    if S[i]=='R':
        j=i
        while S[j]=='R':
            j+=1
        if (j-i)%2==0:
            T[j]+=1
        elif (j-i)%2==1:
            T[j-1]+=1
    else:
        j=i
        while S[j]=='L':
            j-=1
        if (i-j)%2==0:
            T[j]+=1
        elif (j-i)%2==1:
            T[j+1]+=1

ans=''
for k in range(N):
    ans+=str(T[k])+' '

print(ans)



### FIXED CODE ###

#鈴木に教わった

S=str(input())
N=len(S)

ans=[]
for h in range(N):
    ans.append(0)
    
L=[]
count=0
for i in range(N-1):
    if S[i]==S[i+1]:
        count+=1
    else:
        L.append([S[i],count+1])
        count=0

L.append([S[N-1],count+1])

now=0
for j in range(len(L)):
    if L[j][0]=='R':
        now+=L[j][1]
        ans[now]+=L[j][1]//2
        ans[now-1]+=L[j][1]-L[j][1]//2
    else:
        ans[now-1]+=L[j][1]//2
        ans[now]+=L[j][1]-L[j][1]//2
        now+=L[j][1]

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

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

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

t = [ 1 for i in range(N) ]
i = 0
for m in range(M):
    if a[m] % 2 == 1:
        s = -1
    else:
        s =  1
    aa = a[m]

    while aa > 0:
        i = (i + s) % N
        if t[i] == 1:
            aa -= 1
    t[i] = 0
    while True:
        i = (i + 1) % N
        if t[i] == 1:
            break;
for i in q:
    print(t[i])



### FIXED CODE ###

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

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

t = [ i for i in range(N) ]
n = N
i = 0
for aa in a:
    if aa % 2 == 1:
        i = (i - aa) % n
    else:
        i = (i + aa) % n
    del t[i]
    n -= 1
    
for i in q:
    if i in t:
        print(1)
    else:
        print(0)
### BUGGY CODE ###

N,Y = map(int,input().split())
f = 0

for x in range(2001):
    for y in range(4001):
        for z in range(20001):
            if 10000*x + 5000*y + 1000*z == Y and x + y + z == N:
                print(x,y,z)
                f = 1
                break
        else:
            break
    else:
        break
        
if f == 0:
    print('-1','-1','-1')

### FIXED CODE ###

N,Y = map(int,input().split())
f = 0
loop = 0

for x in range(2001):
    for y in range(2001):
        z = N - x - y
        if 10000*x + 5000*y + 1000*z == Y and z >= 0:
            print(x,y,z)
            f = 1
            loop = 1
            break
    if loop == 1:
        break
if f == 0:
    print('-1','-1','-1')
### BUGGY CODE ###

import sys
import collections
sys.setrecursionlimit(10 ** 8)

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = collections.Counter(ZZ())
    e = collections.defaultdict(list)

    def yakusu(num):
        i = 1
        ret = []
        while i*i <= num:
            if num%i != 0:
                i += 1
                continue
            ret.append(i)
            if i != num//i: ret.append(num//i)
            i += 1

        return ret

    if 1 in A.keys():
        if A[1] == 1: print(1)
        elif A[1] >= 2: print(0)
        return

    ans = 0
    for n in A.keys(): e[n] = yakusu(n)

    for n in A.keys():
        if A[n] >= 2: continue
        for p in e[n]:
            if p in {1, n}: continue
            if p in A.keys(): break
        else: ans += 1
    print(ans)

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = sorted(ZZ())
    cA = collections.Counter(A)
    MAX_A = 10 ** 6
    is_ok = [True] * (MAX_A + 1)

    if 1 in cA.keys():
        if cA[1] == 1: print(1)
        elif cA[1] >= 2: print(0)
        return

    for a in cA.keys():
        if not is_ok[a]: continue
        if cA[a] >= 2: is_ok[a] = False
        for i in range(2, MAX_A + 1):
            if a * i > MAX_A: break
            is_ok[a * i] = False

    ans = 0
    for a in cA.keys():
        if is_ok[a]: ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()