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

if __name__ == "__main__":
    h, w, k = map(int, input().split())
    s = []

    for _ in range(h):
        si = input()
        s.append(si)
    
    h_split = [0] * (h - 1)
    part = 0
    ans = float('inf')
    for mask in range(1 << (h - 1)):
        g = 0
        g_id = [0] * h
        for i in range(h):
            g_id[i] = g
            if mask >> i & 1 == 1:
                g += 1
        g += 1

        c = []
        for _ in range(g):
            c.append([0] * w)
        
        for i in range(h):
            for j in range(w):
                if s[i][j] == "1":
                    c[g_id[i]][j] += 1
        num = g - 1
        now = [0] * g

        for j in range(w):
            for i in range(g):
                now[i] += c[i][j]
            ok = True
            for i in range(g):
                if now[i] > k:
                    ok = False

            if not ok:
                num += 1
                now = [0] * g
                for i in range(g):
                    now[i] += c[i][j]
                ok = True
                for i in range(g):
                    if now[i] > k:
                        ok = False
                if not ok:
                    num = float('inf')
                    break
        ans = min(ans, num)
    print(ans)

### FIXED CODE ###

if __name__ == "__main__":
    h, w, k = map(int, input().split())
    s = []

    for _ in range(h):
        si = input()
        s.append(si)
    
    h_split = [0] * (h - 1)
    part = 0
    ans = float('inf')
    for mask in range(1 << (h - 1)):
        g = 0
        g_id = [0] * h
        for i in range(h):
            g_id[i] = g
            if mask >> i & 1 == 1:
                g += 1
        g += 1

        c = []
        for _ in range(g):
            c.append([0] * w)
        
        for i in range(h):
            for j in range(w):
                if s[i][j] == "1":
                    c[g_id[i]][j] += 1
        num = g - 1
        now = [0] * g

        for j in range(w):
            for i in range(g):
                now[i] += c[i][j]
            ok = True
            for i in range(g):
                if now[i] > k:
                    ok = False

            if not ok:
                num += 1
                now = [0] * g
                for i in range(g):
                    now[i] += c[i][j]
                ok = True
                for i in range(g):
                    if now[i] > k:
                        ok = False
                if not ok:
                    num = float('inf')
                    break
        ans = min(ans, num)
    print(ans)
### BUGGY CODE ###

from collections import deque


N, M = map(int,input().split())
mymap = [ [] for n in range(N) ]
for m in range(M):
    a, b = map(int, input().split())
    mymap[a-1].append(b-1)
    mymap[b-1].append(a-1)
#print(mymap)
myans = 0
for n in range(N):
    mylist = mymap[n]
    #print(mylist)
    myd = deque()
    for mm in mylist:
        myd.append(mm)
    #print(myd)
    check_list = [0 for n in range(N)]
    mycnt = 1
    check_list[n] = 1
    while myd:
        tgt = myd.popleft()
        #print(tgt)
        if check_list[tgt] == 0 :
            for e in mymap[tgt]:
                if e > n :
                    myd.append(e)
            mycnt += 1
            check_list[tgt] = 1
    if myans < mycnt:
        myans = mycnt
print(myans)

### FIXED CODE ###

from collections import deque


N, M = map(int,input().split())
mymap = [ [] for n in range(N) ]
for m in range(M):
    a, b = map(int, input().split())
    mymap[a-1].append(b-1)
    mymap[b-1].append(a-1)
#print(mymap)
myans = 0
check_list = [0 for n in range(N)]

for n in range(N):
    mylist = mymap[n]
    #print(mylist)
    myd = deque()
    for mm in mylist:
        myd.append(mm)
    #print(myd)
    mycnt = 1
    check_list[n] = 1
    while myd:
        tgt = myd.popleft()
        #print(tgt)
        if check_list[tgt] == 0 :
            for e in mymap[tgt]:
                if e > n :
                    myd.append(e)
            mycnt += 1
            check_list[tgt] = 1
    if myans < mycnt:
        myans = mycnt
print(myans)
### BUGGY CODE ###

# 入力
k,s=map(int,input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if s == x+y+z:
                count += 1
print(count)


### FIXED CODE ###

# 入力
k,s=map(int,input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        if 0 <= (s-x-y) <= k:
            count += 1
print(count)
### BUGGY CODE ###

H,W=map(int,input().split())
S=[]
for i in range(H):
    s=input()
    S.append(s)
L=[[] for _ in range(H)]
R=[[] for _ in range(H)]
D=[[] for _ in range(H)]
U=[[] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            L[i].append(0)
        else:
            if j==0:
                L[i].append(1)
            else:
                L[i].append(L[i][j-1]+1)
for i in range(H):
    for j in range(W):
        if S[i][W-1-j]=="#":
            R[i].append(0)
        else:
            if j==0:
                R[i].append(1)
            else:
                R[i].append(R[i][j-1]+1)
for i in range(W):
    for j in range(H):
        if S[j][i]=="#":
            U[j].append(0)
        else:
            if j==0:
                U[j].append(1)
            else:
                U[j].append(U[j-1][i]+1)
for i in range(W):
    for j in range(H):
        if S[H-1-j][i]=="#":
            D[j].append(0)
        else:
            if j==0:
                D[j].append(1)
            else:
                D[j].append(D[j-1][i]+1)
ans=0

for i in range(H):
    for j in range(W):
        tmp=L[i][j]+R[i][W-1-j]+U[i][j]+D[H-1-i][j]-3
        ans=max(ans,tmp)
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
S=[]
for i in range(H):
    s=input()
    S.append(s)
L=[[0]*W for _ in range(H)]
R=[[0]*W for _ in range(H)]
D=[[0]*W for _ in range(H)]
U=[[0]*W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            if j==0:
                L[i][j]=1
            else:
                L[i][j]=L[i][j-1]+1
for i in range(H):
    for j in range(W-1,-1,-1):
        if S[i][j]==".":
            if j==(W-1):
                R[i][j]=1
            else:
                R[i][j]=R[i][j+1]+1

for j in range(W):
    for i in range(H-1,-1,-1):
        if S[i][j]==".":
            if i==(H-1):
                D[i][j]=1
            else:
                D[i][j]=D[i+1][j]+1

for j in range(W):
    for i in range(H):
        if S[i][j]==".":
            if i==0:
                U[i][j]=1
            else:
                U[i][j]=U[i-1][j]+1
ans=0
X=[[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        X[i][j]=L[i][j]+R[i][j]+D[i][j]+U[i][j]-3
    ans=max(ans,max(X[i]))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
Bridge= [[int(i) for i in input().split()] for _ in range(M)]
Parent = [int(i) for i in range(N)]
Rank = [1] * N

def find(x):
    if x == Parent[x]: return x
    else:
        Parent[x] = find(Parent[x])
        return Parent[x]

def unite(x, y, Total):
    rx, ry = find(x), find(y)
    if rx == ry: return Total
    Total -= Rank[rx] * Rank[ry]
    Parent[rx] = ry
    Rank[ry] += Rank[rx]
    return Total

Total = N * (N - 1) // 2
Ans = str(Total)
for i in reversed(range(1, M)):
    A, B = Bridge[i]
    A -= 1
    B -= 1
    Total = unite(A, B, Total)
    Ans = str(Total) + "\n" + Ans  

print(Ans)

### FIXED CODE ###

N, M = map(int, input().split())
Bridge= [[int(i) for i in input().split()] for _ in range(M)]
Parent = [int(i) for i in range(N)]
Rank = [1] * N
 
def find(x):
    if x == Parent[x]: return x
    else:
        Parent[x] = y = find(Parent[x])
        return y
 
def unite(x, y, Total):
    rx, ry = find(x), find(y)
    if rx == ry: return Total
    else:
      Total -= Rank[rx] * Rank[ry]
      if Rank[rx] < Rank[ry]:
        Parent[rx] = ry
        Rank[ry] += Rank[rx]
      else:
        Parent[ry] = rx
        Rank[rx] += Rank[ry]
      return Total
 
Total = N * (N - 1) // 2
Ans = [Total] * M
for i in reversed(range(1, M)):
    A, B = Bridge[i]
    Total = unite(A-1, B-1, Total)
    Ans[i-1] = Total  
 
print("\n".join(map(str, Ans)))
### BUGGY CODE ###

from operator import itemgetter

N, M = map(int, input().split())
job_list = []
for i in range(M):
    job_list.append([])
for i in range(N):
    day, pay = map(int, input().split())
    if(day - 1 < M):
        job_list[day-1].append(pay)

now_date = 0
money = 0
now_job_list = []
for i in range(M):
    now_job_list.extend(job_list[i])
    if(len(now_job_list) > 0):
        now_job_list.sort()
        money += now_job_list.pop()
print(money)


### FIXED CODE ###

N, M = map(int, input().split())
job_list = {}
for i in range(N):
	day, pay = map(int, input().split())
	if((day-1) in job_list):
		job_list[day-1].append(pay)
	else:
		job_list[day-1] = [pay]

now_date = 0
money = 0
now_job_list = []
sorted = False
for i in range(M):
	if(i in job_list):
		now_job_list.extend(job_list[i])
		sorted = False
	if(len(now_job_list) > 0):
		if(not sorted):
			now_job_list.sort()
			sorted = True
		money += now_job_list.pop()
print(money)
### BUGGY CODE ###

n = int(input())
A = []
for i in range(n):
    a = int(input())
    if a not in A:
        A.append(a)
    else:
        A.remove(a)
print(len(A))

### FIXED CODE ###

from collections import Counter
n = int(input())
A = [0]*n
for i in range(n):
    A[i] = int(input())

cA = Counter(A).values()
r = 0
for i in cA:
    r += i%2
print(r)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
import copy

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
q=deque()
q.append(N)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in rev_al[fro]:
		if Visit[to]==0:
			q.append(to)
			
Visit1=Visit

#スタートからBFS
q=deque()
q.append(1)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in al[fro]:
		if Visit[to]==0:
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))


D=[ float("-inf") for _ in range(N+1) ]	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
for i in range(new_N):
	for a,b,c in fedge:
		if D[a]==float("-inf"): continue
		alt=D[a]+c
		if D[b]<alt:
			D[b]=alt
			if i==new_N-1:
				print -1
				quit()

print max(0,D[N])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(N)
Visit[N]=1
while q:
	fro=q.popleft()
	for to in rev_al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)
			
Visit1=Visit

#スタートからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(1)
Visit[1]=1
while q:
	fro=q.popleft()
	for to in al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))


D=[ float("-inf") ]*(N+1)	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
for i in range(new_N):
	for a,b,c in fedge:
		if D[a]==float("-inf"): continue
		alt=D[a]+c
		if D[b]<alt:
			D[b]=alt
			if i==new_N-1:
				print -1
				quit()

print max(0,D[N])
### BUGGY CODE ###

import heapq
import numpy as np
import sys

class rode():
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return self.y < other.y
    def __gt__(self, other):
        return other > self
    def __le__(self, other):
        return not(other > self)
    def __ge__(self, other):
        return not(self > other)

n,m = map(int,input().split())
da = [[] for i in range(n)]
for i in range(1,n):
    da[i].append([i-1,0])
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
pq=[]
ju = np.zeros(n,dtype=bool)
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, rode(i[0],i[1]))
while(len(pq)):
    now = heapq.heappop(pq)
    if now.x == n-1:
        print(now.y)
        sys.exit()
    if ju[now.x]:
        continue
    ju[now.x] = True
    for i in da[now.x]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,rode(i[0],now.y+i[1]))
print(-1)

### FIXED CODE ###

import heapq
import numpy as np
import sys

n,m = map(int,input().split())
da = [[] for i in range(n)]
for i in range(1,n):
    da[i].append([i-1,0])
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
pq=[]
ju = np.zeros(n,dtype=bool)
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, [i[1],i[0]])
while(len(pq)):
    now = heapq.heappop(pq)
    if now[1] == n-1:
        print(now[0])
        sys.exit()
    if ju[now[1]]:
        continue
    ju[now[1]] = True
    for i in da[now[1]]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,[now[0]+i[1],i[0]])
print(-1)
### BUGGY CODE ###

import collections
n, k = map(int,input().split())
a = list(map(int, input().split()))
c = collections.Counter(a)
ans = 0
if len(set(a)) <= k:
    print(ans)
    exit()
for i in range(k,len(c)):
    ans += c.most_common()[i][1]
print(ans)

### FIXED CODE ###

import collections
n, k = map(int,input().split())
a = list(map(int, input().split()))
c = collections.Counter(a)
ans = 0
cnt = 0
if len(set(a)) <= k:
    print(ans)
    exit()
for  tuple in c.most_common():
    ans += tuple[1]
    cnt += 1
    if cnt == k:
      print(n-ans)
      exit()
### BUGGY CODE ###

N,X,Y=map(int,input().split())
def shortest(x,y,a,b):
    ans=min(y-x,abs(y-b)+1+abs(a-x),abs(y-a)+1+abs(b-x))
    return ans
distance=[0]*(N-1)
for x in range(1,N):
    for y in range(2,N+1):
        if y<=x:
            continue
        a=shortest(x,y,X,Y)
        distance[a-1]+=1
for i in range(N-1):
    print(distance[i])

### FIXED CODE ###

N,X,Y=map(int,input().split())
def shortest(x,y,a,b):
    ans=min(y-x,abs(y-b)+1+abs(a-x),abs(y-a)+1+abs(b-x))
    return ans
distance=[0]*N
for x in range(1,N+1):
    for y in range(1,N+1):
        if y<=x:
            continue
        else:
            a=shortest(x,y,X,Y)
            distance[a-1]+=1
for i in range(N-1):
    print(distance[i])
### BUGGY CODE ###

str_list = input().split(' ')
int_list = [int(x) for x in str_list]
N, K, Q = int_list[0], int_list[1], int_list[2]
A = []
for _ in range(Q):
    A.append( int(input()) )
point = [int(K)]*N
import numpy as np
point = np.array(point)
for ii in range(Q):
    point -= 1
    point[A[ii]-1] += 1
for ii in range(N):
    if point[ii] <= 0:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

str_list = input().split(' ')
int_list = [int(x) for x in str_list]
N, K, Q = int_list[0], int_list[1], int_list[2]
A = []
for _ in range(Q):
    A.append( int(input()) )
point = [int(K)]*N
import numpy as np
point = np.array(point)
for ii in range(Q):
    point[A[ii]-1] += 1
point -= Q
for ii in range(N):
    if point[ii] <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

def f_modularness():
    K, Q = [int(i) for i in input().split()]
    D = [int(i) for i in input().split()]
    Queries = [[int(i) for i in input().split()] for j in range(Q)]

    def divceil(a, b):
        return (a + b - 1) // b

    ans = []
    for n, x, m in Queries:
        last, eq = x, 0  # 末項、D_i % m == 0 となる D_i の数
        for i,d in enumerate(D):
            num = divceil(n - 1 - i, K)  # D_i を足すことは何回起きるか？
            last += (d % m) * num
            if d % m == 0:
                eq += num
        ans.append((n - 1) - (last // m - x // m) - eq)
    return '\n'.join(map(str, ans))

print(f_modularness())

### FIXED CODE ###

def f_modularness():
    K, Q = [int(i) for i in input().split()]
    D = [int(i) for i in input().split()]
    Queries = [[int(i) for i in input().split()] for j in range(Q)]

    def divceil(a, b):
        return (a + b - 1) // b

    ans = []
    for n, x, m in Queries:
        last, eq = x, 0  # 末項、D_i % m == 0 となる D_i の数
        for i,d in enumerate(D):
            num = divceil(n - 1 - i, K)  # D_i を足すことは何回起きるか？
            last += (d % m) * num
            if d % m == 0:
                eq += num
        ans.append((n - 1) - (last // m - x // m) - eq)
    return '\n'.join(map(str, ans))

print(f_modularness())
### BUGGY CODE ###

t=input()
ans=''
for c in t:
  if c=='?':
    ans+='D'
  else:
    ans+=c
print(ans)

### FIXED CODE ###

t=input()
print(t.replace('?','D'))
### BUGGY CODE ###

H = [int(input())]
 
ans = 0
while len(H):
  ans += 1
  m = H.pop(0)
  if m == 1:
    continue
  else:
    H = H + [m//2, m//2]
print(ans)

### FIXED CODE ###

H = int(input())

def f(H):
  if H == 1:
    return 1
  else:
    return 2*f(H//2)+1

print(f(H))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=0.0
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret+=n
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

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

b = list(set(a))
m = len(b)

ans = 0
for i in range(m):
    c = a.count(b[i])
    if b[i] > c: ans += c
    if b[i] < c: ans += c - b[i]

print(ans) 


### FIXED CODE ###

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

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

ans = 0
for i in range(n):
    if a[i] > n:
        ans += 1
    else:
        b[a[i]] += 1 

for i in range(n+1):
    if b[i] > i: ans += b[i] - i
    if b[i] < i: ans += b[i]

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

#!/usr/bin/env python3
import sys


def solve(S: str):
    count = 0
    S = [s for s in S]
    
    while True:
        sub_count = 0
        for i in range(len(S)-1):
            if S[i] == 'B' and S[i+1] =='W':
                S[i], S[i+1] = 'W', 'B'
                sub_count += 1

        if sub_count == 0:
            break
        count += sub_count
        
    print(count)
    return


# Generated by 1.1.7.1 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()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):
    count = 0
    S = [s for s in S]

    count = 0
    sub_count = 0

    for s in S:
        if s == 'W':
            count += sub_count
        else:
            sub_count += 1
                
        
    print(count)
    return


# Generated by 1.1.7.1 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()
    S = next(tokens)  # type: str
    solve(S)

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

# coding: utf-8

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

for i in range(q):
    f,e = (map(int, input().split()))
    st = s[f-1:e]
    count = 0
    for j in range(len(st)-1):
        if st[j] == 'A' and st[j+1] == 'C':
            count += 1
    print(count)


### FIXED CODE ###

# coding: utf-8

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

t = [0]*(n+1)
for i in range(n):
    if s[i:i+2] == 'AC':
        t[i+1] = t[i] + 1
    else:
        t[i+1] = t[i]

for i in range(q):
    l,r = (map(int, input().split()))
    ans = t[r-1] - t[l-1]
    print(ans)
### BUGGY CODE ###

c=[0]*8**7
for a in[*open(i:=0)][1].split():c[int(a)]+=1
while i<1e6:
 i+=1;j=i
 while j<1e6:j+=i;c[j]*=c[i]<1
print(c.count(1))

### FIXED CODE ###

m=8**7
c=[0]*m
for a in[*open(0)][1].split():c[int(a)]+=1
i=r=0
while~i+m:
 i+=1;r+=c[i]==1
 if c[i]:c[::i]=[0]*-(-m//i)
print(r)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
for b,c in bc:
    a.extend([c]*b)
a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

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

total = 0
D = []
A = sorted(A, key=lambda x:x[1], reverse=True)
for b, c in A:
    if len(D) >= N:
        break
    D.extend([c]*b)
print(sum(D[:N]))
### BUGGY CODE ###

import numpy as np

H,N = list(map(int, input().split()))
As = []
Bs = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    As.append(a)
    Bs.append(b)

dp = np.full((N+1, H+1), np.inf)
dp[:, 0] = 0

for r in range(1,N+1):
    for c in range(1,H+1):
        if c >= As[r-1]:
            dp[r, c] = min(dp[r-1, c], dp[r, c-As[r-1]] + Bs[r-1])
        else:
            dp[r, c] = min(dp[r-1, c], Bs[r-1])

# print(dp)
print(int(dp[-1, -1]))


### FIXED CODE ###

import numpy as np

H,N = list(map(int, input().split()))
As = []
Bs = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    As.append(a)
    Bs.append(b)
As = np.array(As)
Bs = np.array(Bs)

dp = np.full((H+1), np.inf)
dp[0] = 0

for c in range(1,H+1):
    dp[c] = np.amin(dp[np.maximum(c - As, 0)] + Bs)

print(int(dp[-1]))