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

N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
    w_tmp,v_tmp=map(int,input().split())
    w.append(w_tmp)
    v.append(v_tmp)

dp=[[ -1 for _ in range(W+1) ] for _  in range(N+1)]
def rec(i,j):
    if dp[i][j] != -1:
        return dp[i][j]
    if i==N:
         res=0
    elif j<w[i]:
        res=rec(i+1,j)
    else:
        res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i])
    dp[i][j]=res
    return res

print(rec(0,W))
    


### FIXED CODE ###

N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
    w_tmp,v_tmp=map(int,input().split())
    w.append(w_tmp)
    v.append(v_tmp)

dp=[{} for _  in range(N+1)]
def rec(i,j):
    if j in dp[i] :
        return dp[i][j]
    if i==N:
         res=0
    elif j<w[i]:
        res=rec(i+1,j)
    else:
        res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i])
    dp[i][j]=res
    
    return res

print(rec(0,W))
### BUGGY CODE ###

from collections import deque
N = int(input())
connected = [[] for _ in range(N)]
ans = [0] * (N-1)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append([b,i])
    connected[b-1].append([a,i])
colors = max(len(d) for d in connected)
print(colors)
init = 1
d = deque()
parents = deque()
for edge in connected[0]:
    ans[edge[1]] = init
    init += 1
    d.append(edge)
    parents.append(1)
while d:
    temp = d.popleft()
    parent = parents.popleft()
    if len(connected[temp[0]-1]) > 1:
        used = deque(range(1,colors+1))
        used.remove(ans[temp[1]])
        for edge in connected[temp[0]-1]:
            if edge[0] != parent:
                ans[edge[1]] = used.popleft()
                d.append(edge)
                parents.append(temp[0])
for i in range(N-1):
    print(ans[i])

### FIXED CODE ###

from collections import deque
N = int(input())
connected = [[] for _ in range(N)]
ans = [0] * (N-1)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append([b,i])
    connected[b-1].append([a,i])
colors = max(len(d) for d in connected)
print(colors)
init = 1
d = deque()
parents = deque()
for edge in connected[0]:
    ans[edge[1]] = init
    init += 1
    d.append(edge)
    parents.append(1)
while d:
    temp = d.popleft()
    parent = parents.popleft()
    l = len(connected[temp[0]-1])
    if l > 1:
        used = deque(range(1,l+1))
        for edge in connected[temp[0]-1]:
            if edge[0] != parent:
                color = used.popleft()
                if color == ans[temp[1]]:
                    ans[edge[1]] = used.popleft()
                else:
                    ans[edge[1]] = color
                d.append(edge)
                parents.append(temp[0])
for i in range(N-1):
    print(ans[i])
### BUGGY CODE ###

# coding: utf-8
from collections import deque
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
D = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        D[i][j] = abs(j-i)
        D[j][i] = abs(j-i)
D[X][Y] = 1
D[Y][X] = 1
# print(*D, sep="\n")
queue = deque([[X, Y]])
visited = [[False for _ in range(N)] for _ in range(N)]
visited[X][Y] = True 
while queue:
    x,y = queue.popleft()
    for i, j in zip([1, 0, -1, 0], [0, 1, 0, -1]):
        nx, ny = x+i, y+j
        if nx < 0 or nx >= N or ny < 0 or ny >= N:
            continue
        if visited[nx][ny]:
            continue
        else:
            visited[nx][ny] = True
            D[nx][ny] = min(D[nx][ny], D[x][y]+1)
            queue.append([nx, ny])
# print(*D, sep="\n")
ans = [0 for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        # cnt += 1
        v = D[i][j]
        # print(i,j, v)
        ans[v-1] += 1
print(*ans[:-1], sep="\n")

### FIXED CODE ###

# coding: utf-8
from collections import deque
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
D = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        D[i][j] = abs(j-i)
        D[j][i] = abs(j-i)
D[X][Y] = 1
D[Y][X] = 1
# print(*D, sep="\n")
queue = deque([[X, Y]])
visited = [[False for _ in range(N)] for _ in range(N)]
visited[X][Y] = True 
while queue:
    x,y = queue.popleft()
    for i, j in zip([1, 0, -1, 0], [0, 1, 0, -1]):
        nx, ny = x+i, y+j
        if nx < 0 or nx >= N or ny < 0 or ny >= N:
            continue
        if visited[nx][ny]:
            continue
        else:
            visited[nx][ny] = True
            D[nx][ny] = min(D[nx][ny], D[x][y]+1)
            queue.append([nx, ny])
# print(*D, sep="\n")
ans = [0 for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        # cnt += 1
        v = D[i][j]
        # print(i,j, v)
        ans[v-1] += 1
print(*ans[:-1], sep="\n")
### BUGGY CODE ###

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

while abs(N-K) < N:
    N -= K
print(abs(N))



### FIXED CODE ###

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

t = N//K
N -= t*K

while abs(N-K) < N:
    N -= K
print(abs(N))
### BUGGY CODE ###

from collections import deque
import copy

n = int(input())
s = str(input())

dq_s = deque([])
for x in s:
    dq_s.append(x)

dq_s_shift = copy.deepcopy(dq_s)

ans = 0

for i in range(n):
    dq_s_shift.appendleft('_')
    count = 0
    # print(s)
    # print(s_shift)

    for j in range(n):
        if dq_s[j] == dq_s_shift[j]:
            count += 1
        else:
            count = 0
        if count >= ans and count <= i+1:
            ans = count
    # print('-'*30)
    # print(ans)

print(ans)

### FIXED CODE ###

from collections import deque
import copy

n = int(input())
s = str(input())

dq_s = deque([])
for x in s:
    dq_s.append(x)

dq_s_shift = copy.deepcopy(dq_s)

ans = 0

for i in range(n):
    dq_s_shift.appendleft('_')
    count = 0
    # print(s)
    # print(s_shift)

    for j in range(i+1,n):
        if dq_s[j] == dq_s_shift[j]:
            count += 1
        else:
            count = 0
        if count >= ans and count <= i+1:
            ans = count
    # print('-'*30)
    # print(ans)

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


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

wv = [[0 for i in range(2)] for j in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    wv[i+1][0],wv[i+1][1] = map(int, input().split())

wv.sort()

for i in range(N):
    Wsum[i+1] = Wsum[i] + wv[i+1][0]
    Vsum[i+1] = Vsum[i] + wv[i+1][1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #制約が0のときも価値は0
    if W2 == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は入れられない
    if W2 < wv[i][0]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値
    if Wsum[i] <= W2:
        return Vsum[i]

    return max( nap(i-1,W2-wv[i][0])+wv[i][1] , nap(i-1,W2) )
    
            
print(nap(N,W))


### FIXED CODE ###


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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w[i],v[i] = map(int, input().split())
Wmin = min(w)

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))
### BUGGY CODE ###

s = input()
sl = len(s)
dp = {}
ct = [0] * sl
for x in range(sl):
    dp[(0, x)] = x - 1 if s[x] == 'L' else x + 1
for i in range(32):
    for j in range(sl):
        dp[(i + 1, j)] = dp[(i, dp[(i, j)])]
for x in range(sl): ct[dp[(32, x)]] += 1
print(' '.join([str(ct[x]) for x in range(sl)]))

### FIXED CODE ###

s = input()
sl = len(s)
dp = {}
ct = [0] * sl
for x in range(sl):
    dp[(0, x)] = x - 1 if s[x] == 'L' else x + 1
for i in range(17):
    for j in range(sl):
        dp[(i + 1, j)] = dp[(i, dp[(i, j)])]
for x in range(sl): ct[dp[(17, x)]] += 1
print(' '.join([str(ct[x]) for x in range(sl)]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

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

graph = [[] for _ in range(n + 1)]

for i in range(m):
    f, t = map(int, input().split())
    graph[t].append(f)

dp = [-1] * (n + 1)
def dfs(now):
    if dp[now] != -1:
        return dp[now]

    if not graph[now]:
        return 0

    r = max(dfs(parent) for parent in graph[now]) + 1
    dp[now] = r
    return r

print(max(dfs(i) for i in range(1, n + 1)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

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

graph = [[] for _ in range(n + 1)]

for i in range(m):
    f, t = map(int, input().split())
    graph[t].append(f)

dp = [-1] * (n + 1)
def dfs(now):
    if dp[now] != -1:
        return dp[now]

    if not graph[now]:
        return 0

    r = max(dfs(parent) for parent in graph[now]) + 1
    dp[now] = r
    return r

print(max(dfs(i) for i in range(1, n + 1)))
### BUGGY CODE ###

def D_Axis_Parallel_Rectangle(N, K, P):
    x = [0 for _ in range(N)]  # 点のx座標
    y = [0 for _ in range(N)]  # y座標
    x_array = [0 for _ in range(N)]
    y_array = [0 for _ in range(N)]
    for i in range(N):
        x[i] = P[i][0]
        y[i] = P[i][1]
        x_array[i] = x[i]
        y_array[i] = y[i]

    x_array = sorted(x_array)
    y_array = sorted(y_array)

    # すべての点を内部に含む、最大の面積を持つ矩形が初期値
    ans = (x_array[N - 1] - x_array[0]) * (y_array[N - 1] - y_array[0])

    # 全探索
    for xi in range(0, N, 1):
        for xj in range(xi + 1, N, 1):
            for yi in range(0, N, 1):
                for yj in range(yi + 1, N, 1):
                    num = 0
                    left = x_array[xi]
                    right = x_array[xj]
                    bottom = y_array[yi]
                    upper = y_array[yj]

                    for i in range(N):
                        if(left <= x[i] and x[i] <= right and bottom <= y[i] and y[i] <= upper):
                            num += 1
                    if num >= K:
                        ans = min(ans, (right - left) * (upper - bottom))
    return ans

N,K = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(N)]
print(D_Axis_Parallel_Rectangle(N, K, P))

### FIXED CODE ###

def D_Axis_Parallel_Rectangle(N, K, P):
    x = [0 for _ in range(N)]  # 点のx座標
    y = [0 for _ in range(N)]  # y座標
    x_array = [0 for _ in range(N)]
    y_array = [0 for _ in range(N)]
    for i in range(N):
        x[i] = P[i][0]
        y[i] = P[i][1]
        x_array[i] = x[i]
        y_array[i] = y[i]

    x_array = sorted(x_array)
    y_array = sorted(y_array)

    # すべての点を内部に含む、最大の面積を持つ矩形が初期値
    ans = (x_array[N - 1] - x_array[0]) * (y_array[N - 1] - y_array[0])

    # 全探索
    for xi in range(0, N, 1):
        for xj in range(xi + 1, N, 1):
            for yi in range(0, N, 1):
                for yj in range(yi + 1, N, 1):
                    num = 0
                    left = x_array[xi]
                    right = x_array[xj]
                    bottom = y_array[yi]
                    upper = y_array[yj]

                    for i in range(N):
                        if(left <= x[i] and x[i] <= right and bottom <= y[i] and y[i] <= upper):
                            num += 1
                    if num >= K:
                        ans = min(ans, (right - left) * (upper - bottom))
    return ans

N,K = [int(i) for i in input().split()]
P = [[int(i) for i in input().split()] for j in range(N)]
print(D_Axis_Parallel_Rectangle(N, K, P))
### BUGGY CODE ###

n = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for i in range(1,n-1):
  for j in range(i):
    if L[n-1] - L[i]-L[j] < 0:
      ans += (n-1) - (i+1) + 1
      continue
    elif L[i+1] - L[i]-L[j] >= 0:
      continue
    l = i+1
    r = n-1
    while abs(r-l) > 1:
      mid = (l+r)//2
      if L[i]+L[j] - L[mid]> 0:
        l = mid
      else:
        r= mid
    ans += l-(i+1)+ 1
print(ans)

### FIXED CODE ###

n = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for i in range(1,n-1):
  for j in range(i):
    if L[n-1] - L[i]-L[j] < 0:
      ans += (n-1) - (i+1) + 1
      continue
    elif L[i+1] - L[i]-L[j] >= 0:
      continue
    l = i+1
    r = n-1
    while abs(r-l) > 1:
      mid = (l+r)//2
      if L[i]+L[j] - L[mid]> 0:
        l = mid
      else:
        r= mid
    ans += l-(i+1)+ 1
print(ans)
### BUGGY CODE ###

h, n = map(int, input().strip().split())
# AB = [list(map(int, input().split())) for i in range(n)]

dp=[10**9]*(h+1)

dp[0]=0
for _ in range(n):
    a, b = map(int, input().strip().split())
    for i in range(h):
        ni=min(i+a,h)
        dp[ni] = min(dp[ni],dp[i]+b)
        
print(dp[h])

### FIXED CODE ###

h, n = map(int, input().strip().split())
# AB = [list(map(int, input().split())) for i in range(n)]

dp=[10**9]*(h+1)

dp[0]=0
for _ in range(n):
    a, b = map(int, input().strip().split())
    for i in range(h):
        ni=min(i+a,h)
        dp[ni] = min(dp[ni],dp[i]+b)
        
print(dp[h])
### BUGGY CODE ###

import sys
import heapq

input = sys.stdin.readline


def main():
    X, Y, Z, K = map(int, input().split())
    A = list(map(lambda x: -int(x), input().split()))
    B = list(map(lambda x: -int(x), input().split()))
    C = list(map(lambda x: -int(x), input().split()))

    A.sort()
    B.sort()
    C.sort()

    p_queue = [(A[0] + B[0] + C[0], 0, 0, 0)]
    appear = [[[False for _ in range(Z)] for _ in range(Y)] for _ in range(X)]
    appear[0][0][0] = True
    ans = []
    while len(ans) < K:
        s, i_A, i_B, i_C = heapq.heappop(p_queue)
        ans.append(-s)
        if i_A < X - 1 and not appear[i_A + 1][i_B][i_C]:
            appear[i_A + 1][i_B][i_C] = True
            t = s - A[i_A] + A[i_A + 1]
            p_queue.append((t, i_A + 1, i_B, i_C))
        if i_B < Y - 1 and not appear[i_A][i_B + 1][i_C]:
            appear[i_A][i_B + 1][i_C] = True
            t = s - B[i_B] + B[i_B + 1]
            p_queue.append((t, i_A, i_B + 1, i_C))
        if i_C < Z - 1 and not appear[i_A][i_B][i_C + 1]:
            appear[i_A][i_B][i_C + 1] = True
            t = s - C[i_C] + C[i_C + 1]
            p_queue.append((t, i_A, i_B, i_C + 1))

        heapq.heapify(p_queue)

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline


def main():
    X, Y, Z, K = map(int, input().split())
    A = list(map(lambda x: -int(x), input().split()))
    B = list(map(lambda x: -int(x), input().split()))
    C = list(map(lambda x: -int(x), input().split()))

    A.sort()
    B.sort()
    C.sort()

    p_queue = [(A[0] + B[0] + C[0], 0, 0, 0)]
    visited = set()
    visited.add((0, 0, 0))
    ans = []
    while len(ans) < K:
        s, i_A, i_B, i_C = heapq.heappop(p_queue)
        ans.append(-s)
        if i_A < X - 1 and (i_A + 1, i_B, i_C) not in visited:
            visited.add((i_A + 1, i_B, i_C))
            t = s - A[i_A] + A[i_A + 1]
            heapq.heappush(p_queue, (t, i_A + 1, i_B, i_C))
        if i_B < Y - 1 and (i_A, i_B + 1, i_C) not in visited:
            visited.add((i_A, i_B + 1, i_C))
            t = s - B[i_B] + B[i_B + 1]
            heapq.heappush(p_queue, (t, i_A, i_B + 1, i_C))
        if i_C < Z - 1 and (i_A, i_B, i_C + 1) not in visited:
            visited.add((i_A, i_B, i_C + 1))
            t = s - C[i_C] + C[i_C + 1]
            heapq.heappush(p_queue, (t, i_A, i_B, i_C + 1))

    print("\n".join(map(str, ans)))


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

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append((i, l-1, r-1))

class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.bit = [0]*n
    
    def add(self, i, w):
        x = i+1
        while x<=self.n:
            self.bit[x-1] += w
            x += x & -x
    
    def sum_(self, i):
        ret = 0
        x = i+1
        while x>0:
            ret += self.bit[x-1]
            x -= x & -x
        return ret

bit = BinaryIndexedTree(n+1)
query.sort(key=lambda x:x[2])
last = [None]*n
ans = [None]*q
nr = -1
for idx, l, r in query:
    for cr in range(nr+1, r+1):
        if last[c[cr]] is not None:
            bit.add(last[c[cr]]+1, -1)
        last[c[cr]] = cr
        bit.add(cr+1, 1)
    nr = r
    ans[idx] = bit.sum_(r+1) - bit.sum_(l)
print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append((i, l-1, r-1))

class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.bit = [0]*n
    
    def add(self, i, w):
        x = i+1
        while x<=self.n:
            self.bit[x-1] += w
            x += x & -x
    
    def sum(self, i):
        ret = 0
        x = i+1
        while x>0:
            ret += self.bit[x-1]
            x -= x & -x
        return ret

bit = BinaryIndexedTree(n+1)
query.sort(key=lambda x:x[2])
last = [None]*n
ans = [None]*q
nr = -1
for idx, l, r in query:
    for cr in range(nr+1, r+1):
        if last[c[cr]] is not None:
            bit.add(last[c[cr]]+1, -1)
        last[c[cr]] = cr
        bit.add(cr+1, 1)
    nr = r
    ans[idx] = bit.sum(r+1) - bit.sum(l)
for i in ans:
    print(i)
### BUGGY CODE ###

n=int(input())
mod=10**9+7
X=[]
for i in range(n):
  X.append([int(input()),0])
for i in range(n):
  X.append([int(input()),1])
X.sort(key=lambda x:x[0])
ct=0
Y=[]
for a,b in X:
  if b==0:
    ct+=1
  else:
    ct-=1
  Y.append(ct)
ans=1
m,mm=0,1
key=0
for i in range(2*n):
  if Y[i]==0:
    ans*=mm
    m,mm=0,1
  elif m==0:
    m=1
    key=X[i][1]
  else:
    if X[i][1]==key:
      m+=1
      mm*=m
    else:
      m-=1
print(ans%mod)


### FIXED CODE ###

n=int(input())
ans=1
mod=10**9+7
A=[0,0]
AB=[]
for i in range(n):
  a=int(input())
  AB.append((a,0))
for i in range(n):
  b=int(input())
  AB.append((b,1))
AB.sort(key=lambda x:x[0])
for i in range(2*n):
  a,b=AB[i]
  if b==0:
    if A[1]>0:
      ans=(ans*A[1])%mod
      A[1]-=1
    else:
      A[0]+=1
  else:
    if A[0]>0:
      ans=(ans*A[0])%mod
      A[0]-=1
    else:
      A[1]+=1
print(ans)
### BUGGY CODE ###

N,*A = map(int,open(0).read().split())
for i in range(1,N+1):
    print(A.count(i))

### FIXED CODE ###

from collections import Counter

N,*A = map(int,open(0).read().split())
c = Counter(A)
for i in range(1,N+1):
    if i not in c:
        print(0)
    else:
        print(c[i])
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]

ss = set(s)
sd = {}
for i in ss:
    sd[i] = s.count(i)
    
x = max(sd.values())
dl = []

for i in sd.items():
    if i[1] != x:
        dl.append(i[0])
        
for i in dl:
    del sd[i]
        
for i in sorted(sd):
    print(i)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = [input() for _ in range(n)]

scount = Counter(s)
scsort = scount.most_common()
x = scsort[0][1]
anss = []
for i in scsort:
    if i[1] != x:
        break
    anss.append(i[0])

for i in sorted(anss):
    print(i)
### BUGGY CODE ###

N = int(input())

for n in range(1,N+1):
    counter=0
    for x in range(1,n+1):
        if x * x+2*x+3 > N:
            break
        for y in range(1,n+1):
            if x * x + y * y + x * y+x+y+1 > N:
                break
            for z in range(1, n + 1):
                if x * x + y * y + z * z + x * y + y * z + z * x >= N:
                    break
                if x * x + y * y + z * z + x * y + y * z + z * x == n:
                    counter += 1
    print("{}".format(counter))
 




### FIXED CODE ###

N = int(input())

list=[0]*N
for x in range(1,N+1):
    if x * x+2*x+3 > N:
        break
    for y in range(1,N+1):
        if x * x + y * y + x * y+x+y+1 > N:
            break
        for z in range(1, N + 1):
            val=x * x + y * y + z * z + x * y + y * z + z * x
            if val > N:
                break
            list[val - 1] += 1
for i in range(N):
    print("{}".format(list[i]))
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
dic = defaultdict(int)
for a in A:
  dic[a] += 1

A = list(set(A))
A.sort()
B = []
ans = 0
for a in A:
  flag = True
  for b in B:
    if a % b == 0:
      flag = False
      break

  if flag:
    B += [a]
    if dic[a] == 1:
      ans += 1

print(ans)
      

### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
mx = max(A)+1
B = [0]*(mx)
dic = defaultdict(int)
for a in A:
  dic[a] += 1

A = sorted(list(set(A)))
ans = 0
for a in A:
  if B[a] == 0:
    if dic[a] == 1:
      ans += 1
  for i in range(a, mx, a):
    B[i] += 1

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

def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = input()

    ans = 0
    if P == 5 or P == 2:
        for j in range(1, N+1):
            # j文字取る
            num = int(S[:j])
            if num % P == 0:
                ans += j
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1]):
            # print(i, s)
            s = int(s)
            acc[i+1] = (s * d + acc[i]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = [int(s) for s in input()]

    ans = 0
    if P == 5 or P == 2:
        for i, s in enumerate(S, start=1):
            # j文字取る
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            # print(i, s)
            acc[i] = (s * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


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

# coding=utf-8

n = int(input())
dic_list = []

for i in range(n):
    cmd = input().split()
    if cmd[0] == 'insert':
        dic_list.append(cmd[1])
    else:
        if cmd[1] in dic_list:
            print('yes')
        else:
            print('no')

### FIXED CODE ###

# coding=utf-8

n = int(input())
dic = set()

for i in range(n):
    cmd = input().split()
    if cmd[0] == 'insert':
        dic.add(cmd[1])
    else:
        if cmd[1] in dic:
            print('yes')
        else:
            print('no')
### BUGGY CODE ###

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

### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))
    product = arr[0]
    if 0 in arr:
        product = 0
    else:
        for i in range(1, n):
            product *= arr[i]
            if product > (10**18):
                product = -1
                break
    print(product)