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


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()

if M == N-1: # 一本道
    for _ in range(M):
        s,t = inpl()
    print(M)
else:
    lines = defaultdict(set)
    LL = [0]*N
    for _ in range(M):
        s,t = inpl()
        s -= 1; t -= 1
        lines[s].add(t)
        LL[s] += 1


    def dfs(s):
        global MEMO
        if MEMO[s] != -1:
            return MEMO[s]
        else:
            tmp = 0
            for t in lines[s]:
                tmp += dfs(t) + 1
            L = len(lines[s])
            MEMO[s] = tmp / LL[s]
            return MEMO[s]

    ans = 10**10
    for s in range(N-1):
        for t in lines[s]:
            if LL[s] == 1:
                continue
            MEMO = [-1]*N
            MEMO[-1] = 0
            lines[s].remove(t)
            LL[s] -= 1
            tmp = dfs(0)
            #print(s,t,tmp)
            ans = min(ans,tmp)
            lines[s].add(t)
            LL[s] += 1
    print(ans)


### FIXED CODE ###


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()

if M == N-1: # 一本道
    for _ in range(M):
        s,t = inpl()
    print(M)
else:
    lines = defaultdict(set)
    LL = [0]*N
    for _ in range(M):
        s,t = inpl()
        s -= 1; t -= 1
        lines[s].add(t)
        LL[s] += 1

    def dfs(s):
        global MEMO
        if MEMO[s] != -1:
            return MEMO[s]
        else:
            tmp = 0
            for t in lines[s]:
                if MEMO[t] != -1:
                    tmp += MEMO[t] + 1
                else:
                    tmp += dfs(t) + 1
            MEMO[s] = tmp / LL[s]
            return MEMO[s]

    MEMO = [-1]*N
    MEMO[-1] = 0
    dfs(0)
    koho = [-1]*N
    for s in range(N):
        x = -1
        for t in lines[s]:
            if x < MEMO[t]:
                x = MEMO[t]
                koho[s] = t

    ans = 10**10
    for s in range(N-1):
        t = koho[s]
        if LL[s] == 1 or t == -1:
            continue
        MEMO = [-1]*N
        MEMO[-1] = 0
        lines[s].remove(t)
        LL[s] -= 1
        ans = min(ans,dfs(0))
        lines[s].add(t)
        LL[s] += 1
    print(ans)
### BUGGY CODE ###

from fractions import gcd

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

MOD = 10 ** 9 + 7

tmp = 1
for a in A:
    tmp *= a // gcd(tmp, a)

ans = 0
for a in A:
    ans += tmp // a
    ans %= MOD

print (ans)

### FIXED CODE ###

def main():
    from fractions import gcd

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

    MOD = 10 ** 9 + 7

    tmp = 1
    for a in A:
        tmp *= a // gcd(tmp, a)

    ans = 0
    for a in A:
        ans += tmp // a
    ans %= MOD

    print (ans)

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

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

x=(a*1)//b-a*(1//b)
for i in range(1,n+1):
    x=max(x,(a*i)//b-a*(i//b))

print(x)

### FIXED CODE ###

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

if b>n:
    print((a*n)//b-a*(n//b))
else:
    print((a*(b-1)//b-a*((b-1)//b)))
### BUGGY CODE ###

from subprocess import call
call (('pypy3', '-c', """
import queue
 
def main():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        grid[i] = list(input())


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Queue()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)
    
    return
    
main()
 
"""))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
### BUGGY CODE ###

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

mod = int(1e9+7)
def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod

powerdict = {}
def powermod(p,n,mod):
  if (p,n) in powerdict:
    return powerdict[(p,n)]
  if n==0:
    powerdict[(p,n)] = 1
  if n==1:
    powerdict[(p,n)]=p%mod
  else:
    powerdict[(p,n)] = powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
  return powerdict[(p,n)]

def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)

LR = [1]*(n+2) #LR[k] = (L+R)C(k)
LDR = [0]*(n+2)
LDDR = [0]*(n+2)

_LCR = [1] * (n+2) # _LCR[k] = (L+C+R)C(k)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
LDCR = [0] * (n+2) #最後に*2を忘れないこと
LDCDR = [0] * (n+2)

for k in range(1,n+2):
  LR[k] = (LR[k-1] * (L+R+1-k)) %mod * powermod(k,mod-2,mod)
  LDR[k] = LR[k-1]
  LDDR[k] = LDR[k-1]
  
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod * powermod(k,mod-2,mod)
  
  LCR[k] = _LCR[k] - LR[k]
  LDCR[k] = LCR[k-1]
  LDCDR[k] = LDCR[k-1]
  
  print((LR[k] + LDR[k] + LDDR[k] + LCR[k] + 2*LDCR[k] + LDCDR[k])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

### FIXED CODE ###

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

mod = int(1e9+7)
def powermod(p,n,mod):
    #if n==0: return 1
    if n==1:
        return p%mod
    if n%2:
        return powermod(p,n//2,mod)**2 * p %mod
    else:
        return powermod(p,n//2,mod)**2 %mod


memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [0]*(n+3)
_LCR = [0] * (n+3) # _LCR[k] = (L+C+R)C(k)
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) #LR[k] = (L+R)C(k)
LR[0] = 1
#LDR = [0]*(n+2)
#LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
#LDCR = [0] * (n+2) #最後に*2を忘れないこと
#LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * powermod(k, mod-2, mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
#  LDR[k] = LR[k-1]
#  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]
#  LDCR[k] = LCR[k-1]
#  LDCDR[k] = LDCR[k-1]
  #print(LR, LCR)
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)
### BUGGY CODE ###

n = int(input())
orig_n = n

res=[]
i = 2
while i <= (orig_n // 2):
    if n % i == 0:
        n = n // i
        res.append(i)
        i = 1
    i += 1
if len(res) == 0 : res.append(orig_n)
print("{0}: {1}".format(orig_n, " ".join(map(str, res))))

### FIXED CODE ###

n = int(input())
orig_n = n
res=[]
i = 2
half_n = n // 2
root_n = int(n ** (1/2))
is_prime = True
while i <= (root_n):
    if orig_n % i == 0:
        is_prime = False
        break
    i += 1
if is_prime: res.append(orig_n)

while i <= half_n and not(is_prime):
    if n ==1:
        break
    if n % i == 0:
        n = n // i
        res.append(i)
        i = 1
    i += 1

print("{0}: {1}".format(orig_n, " ".join(map(str, res))))
### BUGGY CODE ###

from itertools import combinations
n = int(input())
s = input()

print(len(set(combinations(s, 3))))


### FIXED CODE ###

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

passwd = ["{:03}".format(x) for x in range(1000)]
ans = 0

for p in passwd:
    p = iter(p)
    c = next(p)
    n = 0
    for t in s:
        if c == t:
            n += 1
            if n == 3:
                ans += 1
                break
            c = next(p)

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

import heapq

N,M = map(int,input().split())
Price_List = list(map(lambda x:x*(-1),map(int,input().split())))
heapq.heapify(Price_List)
for i in range(M):
    heapq.heapify(Price_List)
    val = heapq.heappop(Price_List)* -1 // 2 * -1
    heapq.heappush(Price_List,val)
print(-sum(Price_List))

### FIXED CODE ###

import bisect
 
N,M = map(int,input().split())
Price_List = list(map(int,input().split()))
Price_List.sort()
for i in range(M):
    New_Price = Price_List.pop(-1)//2
    Price_List.insert(bisect.bisect(Price_List,New_Price),New_Price)
print(sum(Price_List))
### BUGGY CODE ###

from collections import Counter

N=int(input())
A=list(map(int,input().split()))
nmax=10**6
iscop=[True]*(nmax+1)
cnt=[0]*(nmax+1)

for a in A:
    cnt[a]+=1
    if iscop[a]==False:
        continue

    for j in range(2,nmax//a+1):
        iscop[j*a]=False
ans=0
for a in A:
    if cnt[a]<2 and iscop[a]:
        ans+=1

print(ans)

### FIXED CODE ###

from collections import Counter

N=int(input())
A=Counter(list(map(int,input().split())))
nmax=10**6
iscop=[True]*(nmax+1)

for k in A.keys():
    if iscop[k]==False:
        continue

    for j in range(2,nmax//k+1):
        iscop[k*j]=False
ans=0
for k,v in A.items():
    if v<2 and iscop[k]:
        ans+=1

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

N = int(input())
ans = 0
A=[]

for i in range(N):
    S=input()
    if S in A:
        continue
    else:
        A.append(S)
        ans+=1

print(ans)

### FIXED CODE ###

N = int(input())
A=[]
 
for i in range(N):
    S=input()
    A.append(S)
 
print(len(list(set(A))))
### BUGGY CODE ###

x=int(input())
a=list(range(2,100000))
for i in  range(len(a)):
    for k in range(len(a)):
        if  a[i]<a[k] and a[i]!=0 and a[k]%a[i]==0:
            a[k]=0
#以上までで合成数を0にした2から99のリストができる
##print([i for i in a if i!=0])
#↑これで0を除ける．むずいね
q=[i for i in a if i!=0]
ans=[0]*(10**5+1)
for i in range(10**5):
    ans[i+1]=ans[i]+(1 if i+1 in q and (i+1+1)//2 in q else 0 )
for i in range(x):
    l,r = map(int,input().split())	
    print(ans[r]-ans[l-1])

### FIXED CODE ###

x=int(input())
n=10**5
import math
def eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q=eratosthenes(n)

ans=[0]*(10**5+1)
for i in range(10**5):
    ans[i+1]=ans[i]+(1 if i+1 in q and (i+1+1)//2 in q else 0 )
for i in range(x):
    l,r = map(int,input().split())	
    print(ans[r]-ans[l-1])
### BUGGY CODE ###

s=input()
l=[0]*2019
while s:
    l[int(s)%2019]+=1
    s=s[1:]

ans=0
for i in l:
    ans+=(i-1)*i//2
print(ans+l[0])

### FIXED CODE ###

s=input()
a=0
now=1
l=[0]*2019
for i in list(s)[::-1]:
    a=(a+now*int(i))%2019
    l[a]+=1

    now*=10
    now%=2019
ans=0
for i in l:
    ans+=(i-1)*i//2
print(ans+l[0])
### BUGGY CODE ###

_=input()
val=1
for i in input().split():
  val*=int(i)
if val>10**18:
  print(-1)
  exit()

print(val)

### FIXED CODE ###

_=input()
val=1
t=10**18

for i in map(int,input().split()):
  if i==0:
    val*=i
    break
  if val>=t: continue
  val*=i

if val>t:
  print(-1)
  exit()

print(val)
### BUGGY CODE ###

n, w = map(int, input().split())
import numpy as np
dp = np.zeros((n+1, w+1))
for i in list(range(n+1))[1:]:
    wi, vi = map(int, input().split())
    for j in range(w+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi]+vi) if j >= wi else dp[i-1][j]
print(int(max(dp[-1])))

### FIXED CODE ###

n, w = map(int, input().split())
import numpy as np
dp = np.zeros(w+1, np.int64)
for i in range(n):
    wi, vi = map(int, input().split())
    np.maximum(dp[:-wi]+vi, dp[wi:], out=dp[wi:])
print(max(dp))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = list(input())
for i in range(Q):
    l,r = map(int,input().split())
    c = 0
    for j in range(l-1,r-1):
        if S[j] == "A" and S[j+1] == "C":
            c += 1
    print(c)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
c = []
count = 0
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        count += 1
    c.append(count)
for i in range(Q):
    l,r = map(int,input().split())
    if l == 1:
        print(c[r-2]-0)
    else:
        print(c[r-2]-c[l-2])
### BUGGY CODE ###

N = int(input())
men = []
for _ in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])

dp = [[float("INF")]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    h,p,a = men[i-1]
    for j in range(1,N+1):
        if dp[i-1][j-1] <= h:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
        else:
            dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j] != float("INF"):
        print(j)
        break


### FIXED CODE ###

N = int(input())
men = []
for _ in range(N):
    H,P = map(int,input().split())
    men.append((H,P,H+P))
men.sort(key=lambda x: x[2])

maxH = max(men)[0]
inf = maxH+1
#dp[i][j] -> i人目までみたとき、j人が座布団を積む場合の最小枚数
dp = [[-1]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    h,p,a = men[i-1]
    for j in range(1,N+1):
        if 0 <= dp[i-1][j-1] <= h:
            if dp[i-1][j] == -1:
                dp[i][j] = dp[i-1][j-1]+p
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+p)
        else:
            dp[i][j] = dp[i-1][j]

for j in range(N,-1,-1):
    if dp[-1][j] != -1:
        print(j)
        break
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))
ans=0
m=n
for i in range(1,n+1):
  k=p.index(i)
  if m>k:
    m=k
    ans+=1


print(ans)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
ans = 0
mi = p[0]
 
for i in range(n):
    if p[i] <= mi:
        ans += 1
        mi = p[i]
    
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans =0
seta = set(a)
for i in seta:
    k=a.count(i)
    if i>k:
        ans+=k
    elif i<k:
        ans+=k-i
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans =0
import collections
c = collections.Counter(a)
for i in c.keys():
    if c[i]>i:
        ans+=c[i]-i
    elif c[i]<i:
        ans+=c[i]
print(ans)
### BUGGY CODE ###

a=input().split()
N,A,B=int(a[0]),int(a[1]),int(a[2])
st_a,st_b='',''
for i in range(A):
  st_a+='b'
for i in range(B):
  st_b+='r'
sum=0
b=''
while sum<=N:
  b+=st_a
  sum+=A
  if(sum>=N):
    break
  b+=st_b
  sum+=B
c=b[0:N]
print(c.count('b'))

### FIXED CODE ###

a=input().split()
N,A,B=int(a[0]),int(a[1]),int(a[2])
b=int(N/(A+B))
ans=int(A*b)
if(N-b*(A+B)<=A):
    ans=ans+N-b*(A+B)
else:
    ans+=A
print(int(ans))
### BUGGY CODE ###

import numpy as np
N=input()

lists = []
temp=np.asarray([i for i in range(10)])

dic={0:1}

for i in N:
    new_dic={}
    hoge=list(dic.items())
    if i == "?":
        for amari,count in hoge:
            amari*=10
            for num in temp:
                a = (amari + num) % 13
                if a in new_dic:
                    new_dic[a]+=count
                else:
                    new_dic[a]=count
    else:
        num=int(i)
        for amari,count in hoge:
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    dic = new_dic

try:
    print(dic[5]%(10**9 + 7))
except:
    print(0)

### FIXED CODE ###


N=input()

lists = []
temp=[i for i in range(10)]

MOD=10**9+7

dic={0:1}

for i in N:
    new_dic={}
    hoge=list(dic.items())
    if i == "?":
        for amari,count in hoge:
            amari*=10
            for num in temp:
                a = (amari + num) % 13
                if a in new_dic:
                    new_dic[a]+=count
                else:
                    new_dic[a]=count
    else:
        num=int(i)
        for amari,count in hoge:
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    for key in new_dic:
        new_dic[key] %= MOD
    dic = new_dic

try:
    print(dic[5])
except:
    print(0)
### BUGGY CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

arr = [set() for _ in range(W)]
arr[0].add(0)
for y in range(H):
    nextarr = [set() for _ in range(W)]
    Ay = A[y]
    By = B[y]
    for x in range(W):
        nextset = nextarr[x]
        d = Ay[x] - By[x]
        for n in arr[x]:
            nextset.add(n+d)
            nextset.add(n-d)
        if x >= 1:
            for n in nextarr[x-1]:
                nextset.add(n+d)
                nextset.add(n-d)
    arr = nextarr
print(min([abs(d) for d in arr[-1]]))

### FIXED CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

arr = [set() for _ in range(W)]
arr[0].add(A[0][0] - B[0][0])
for x in range(1, W):
    s = arr[x]
    d = A[0][x] - B[0][x]
    for n in arr[x-1]:
        s.add(abs(n+d))
        s.add(abs(n-d))

for y in range(1, H):
    nextarr = [set() for _ in range(W)]
    Ay = A[y]
    By = B[y]
    dh = H - y - 1
    for x in range(W):
        nextset = nextarr[x]
        d = Ay[x] - By[x]
        dw = W - x - 1
        lim = (dh + dw + 1) * 160
        #lim = 1280
        if x >= 1:
            arr[x] |= nextarr[x-1]
        for n in arr[x]:
            if abs(n+d) <= lim:
                nextset.add(abs(n+d))
            if abs(n-d) <= lim:
                nextset.add(abs(n-d))
    arr = nextarr
print(min([abs(d) for d in arr[-1]]))
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

def main():
    n, m = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]
    A.sort()

    M = []
    max_c = 0
    for l in sys.stdin:
        b, c = [int(e) for e in l.strip().split()]
        max_c = max(max_c, c)
        M.append([b, c])
    last_idx = len(A)
    for i in range(len(A)):
        if max_c < A[i]:
            last_idx = i + 1
            break

    M.sort(key=lambda x: x[1], reverse=True)

    idx = 0
    for m in M:
        b, c = m[0], m[1]
        b_cnt = 0
        for i in range(idx, last_idx):
            if A[i] < c:
                A[i] = c
                b_cnt += 1
                idx += 1
            if b_cnt == b:
                break
    print(sum(A))

main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

input = sys.stdin.readline

def main():
    n, m = [int(e) for e in input().split()]
    A = [int(e) for e in input().split()]
    A.sort()

    M = []
    max_c = 0
    for l in sys.stdin:
        b, c = [int(e) for e in l.strip().split()]
        max_c = max(max_c, c)
        M.append([b, c])
    last_idx = len(A)
    for i in range(len(A)):
        if max_c < A[i]:
            last_idx = i + 1
            break

    M.sort(key=lambda x: x[1], reverse=True)


    idx = 0
    for m in M:
        b, c = m[0], m[1]
        b_cnt = 0
        for i in range(idx, last_idx):
            if A[i] > c:
                break
            if A[i] < c:
                A[i] = c
                b_cnt += 1
                idx += 1
            if b_cnt == b:
                break

    print(sum(A))

main()
### BUGGY CODE ###

n, m = map(int, input().split())
ac_lst = []
for i in range(m):
    a, b = map(int, input().split())
    lst = list(map(int, input().split()))
    ac_lst.append((a, lst))
    
dp = [[10**10] * (2**n) for _ in range(m+1) ]
for i in range(m+1):
    dp[i][0] = 0

for i in range(1, m+1):
    a, c_lst = ac_lst[i-1]
    d = 0
    for k in c_lst:
        d = d | (2**(k-1))
    for j in range(2**n):
        k = j | d
        dp[i][j] = min(dp[i][j], dp[i-1][j])
        dp[i][k] = min(dp[i][k], dp[i-1][k], dp[i-1][j] + a)
        
print(dp[-1][-1]) if dp[-1][-1] != 10**10 else print(-1)

### FIXED CODE ###

n, m = map(int, input().split())
ac_lst = []
for i in range(m):
    a, b = map(int, input().split())
    lst = list(map(int, input().split()))
    ac_lst.append((a, lst))
    
dp = [[10**10] * (2**n) for _ in range(m+1) ]
for i in range(m+1):
    dp[i][0] = 0

for i in range(1, m+1):
    a, c_lst = ac_lst[i-1]
    d = 0
    for k in c_lst:
        d = d | (2**(k-1))
    for j in range(2**n):
        k = j | d
        dp[i][j] = min(dp[i][j], dp[i-1][j])
        dp[i][k] = min(dp[i][k], dp[i-1][k], dp[i-1][j] + a)
        
print(dp[-1][-1]) if dp[-1][-1] != 10**10 else print(-1)
### BUGGY CODE ###

def solve(S):
    ret = 0
    for i in range(len(S)):
        for j in range(i, len(S)):
           ret += 1 if not int(S[i: j + 1]) % 2019 else 0
    return ret

if __name__ == "__main__":
    S = input()
    print(solve(S))

### FIXED CODE ###

MOD = 2019

def solve(S):
    N = len(S)
    dp = [0 for _ in range(MOD)]
    tmp = 0
    ret = 0
    for i in range(N):
        m = (tmp + int(S[i]) * pow(10, N - i - 1, MOD)) % MOD
        ret += dp[m]
        dp[m] += 1
        tmp = m
    ret += dp[0]
    return ret

if __name__ == "__main__":
    S = input()
    print(solve(S))
### BUGGY CODE ###

def main():
    input()
    integars = sorted(int(x) for x in input().split())
    ans = 0
    for i, x in enumerate(integars):
        chosen = True
        for j, y in enumerate(integars):
            if i == j:
                continue
            elif x % y == 0:
                chosen = False
                break
            elif i < j:
                break
        if chosen:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    numbers = int(input())
    array = [int(x) for x in input().split()]
    maximum = 1000001
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = 0
    for x in array:
        if counter[x] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()