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

import numpy as np

def main():
    H,N = [int(x) for x in input().split()]
    A,B = [],[]
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        A.append(a)
        B.append(b)

    # dp = np.full((N+1,H+1),10 ** 18)
    # dp[0][0] = 0
    dp = [float('inf')]*(H+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            # print(i,j,dp[j],A[i],B[i])
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)], dp[j]+B[i])
            # dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            # dp[i+1][min(j+A[i],H)] = min(dp[i+1][j]+B[i], dp[i+1][min(j+A[i],H)])
            # print(dp)
    print(int(dp[H]))


if __name__ == '__main__':
    main()

### FIXED CODE ###

# import numpy as np

def main():
    H,N = [int(x) for x in input().split()]
    A,B = [],[]
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        A.append(a)
        B.append(b)

    # dp = np.full((N+1,H+1),10 ** 18)
    # dp[0][0] = 0
    dp = [float('inf')]*(H+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            # print(i,j,dp[j],A[i],B[i])
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)], dp[j]+B[i])
            # dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            # dp[i+1][min(j+A[i],H)] = min(dp[i+1][j]+B[i], dp[i+1][min(j+A[i],H)])
            # print(dp)
    print(int(dp[H]))


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

n = int(input())
an = [int(num)  for num in input().split()]

answer = 0
for i in range(len(an)):
  answer +=  an[i] * sum(an[i+1:])
print(answer%1000000007)

### FIXED CODE ###

n = int(input())
an = [int(num)  for num in input().split()]

an_total = sum(an)
answer = 0
for i in range(len(an)-1):
  an_total -= an[i]
  answer +=  an[i] * an_total
print(answer%1000000007)
### BUGGY CODE ###

import numpy as np
N,K,Q=map(int,input().split())
A = np.array([K] * N)
B = np.array([-1] *N)
if K>Q:
    for i in range(N):
        print("Yes")
else:
    for i in range(Q):
        a=int(input())-1
        A=A+B
        A[a]+=1
    for k in range(N):
        if A[k]>0:
            print("Yes")
        else:
            print("No")

### FIXED CODE ###

N,K,Q=map(int,input().split())
A = [0] * N
if K>Q:
    for i in range(N):
        print("Yes")
else:
    for i in range(Q):
        a=int(input())-1
        A[a]+=1
    for k in range(N):
        if K>Q-A[k]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

N, M, Q = map(int, input().split())
q = [[int(i) for i in input().split()] for j in range(Q)]

def check(num):
    pre = 0
    for i in range(len(num)):
        if num[i] == 0:
            continue
        if num[i] <= pre:
            return False
        if num[i] > M:
            return False
    else:
        return True

ans = 0
for pattern in range(1 << Q):
    ls = []
    for i in range(Q):
        if pattern & (1 << i):
            ls.append(q[i])
    
    num = [0] * N
    ls = sorted(ls)
    score = 0
    for a, b, c, d in ls:
        if num[a-1] == 0 and num[b-1] == 0:
            num[a-1] = 1
            num[b-1] = c + 1
        elif num[a-1] == 0:
            num[a-1] = num[b-1] - c
        elif num[b-1] == 0:
            num[b-1] = num[a-1] + c
        else:
            if num[b-1] - num[a-1] != c:
                break

        if check(num): score += d
        else: break
    else:
        ans = max(ans, score)

print(ans)

### FIXED CODE ###

import copy

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

def dfs(count, pre, ls):
    if count == N:
        temp = copy.copy(ls)
        num.append(temp)
        return

    for n in range(pre, M+1):
        ls[count] = n
        dfs(count+1, n, ls)
        ls[count] = 0

num = []
ls = [0] * N
dfs(0, 1, ls)

q = [[int(i) for i in input().split()] for j in range(Q)]
ans = 0
for i in range(len(num)):
    n = num[i]
    score = 0
    for j in range(Q):
        a, b, c, d = q[j]
        if n[b-1] - n[a-1] != c:
            continue
        score += d
    else:
        ans = max(ans, score)

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

N,Q = map(int,input().split())
S = input()
AC = []
for i in range(N-1):
  if S[i]+S[i+1] == "AC":
    AC.append(i)
    
for j in range(Q):
  l,r = map(int,input().split())
  cnt = 0
  for k in AC:
    if l-1 <= k <= r-1 and l-1 <= k+1 <= r-1:
      cnt += 1
  print(cnt)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
t = [0]*(N+1)

for i in range(N):
  t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)
  
for j in range(Q):
  l,r = map(int,input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

import math, copy

N = int(input())

A = [0] * 5
A[0] = int(input())
A[1] = int(input())
A[2] = int(input())
A[3] = int(input())
A[4] = int(input())

# 最後に到着する人がかかる時間を求めればよい
# 乗り物に乗れる人数 < 最終グループの人数 が成り立つときに、遅延が発生
P = [0] * 6
Q = [0] * 6
P[0] = N
Q[0] = N
counter = 0

while P[5] != N:
	# print(P)
	# print("/////////")
	counter += 1
	# それぞれのマスiについて
	for i in range(5):
		if A[i] != 0:
			if A[i] >= P[i]: # 移動できる人の数 >= 移動したい人の数
				Q[i + 1] += P[i] # iマス目にいた人をi + 1マス目に移す
				Q[i] -= P[i]
			else: # 遅延が発生
				move_num = A[i] #　このとき、次のマスに行けるのは、A[i]人だけ
				Q[i] -= A[i]
				Q[i + 1] += A[i]
	P = copy.deepcopy(Q) # 状態を更新する
		
print(counter)


### FIXED CODE ###

import math, copy

N = int(input())

A = [0] * 5
A[0] = int(input())
A[1] = int(input())
A[2] = int(input())
A[3] = int(input())
A[4] = int(input())

print(math.ceil(N / min(A) + 4))
### BUGGY CODE ###

A,B,K = map(int,input().split())
for i in range(K):
    if A>0:
        A-=1
    else:
        B-=1
print(A,B)

### FIXED CODE ###

A,B,K = map(int,input().split())
A1=A
if A-K<0:
    A = 0
else:
    A = A - K
K=K-A1
if K >=0:
    B=B-K
if B <0:
    B=0
print(A,B)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

lst = []
for i in A:
    for j in B:
        for k in C:
            lst += [(i + j + k)]

lst.sort(reverse = True)

count = 1
while count <= K:
    print (lst[count-1])
    count += 1 

### FIXED CODE ###

#単純な全探索-->TLE-->Cの配列を扱うときに工夫
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

lst = []
for i in A:
    for j in B:
        lst += [i + j]

lst.sort(reverse = True)
C.sort(reverse = True)

ans = []
for i in range(min(K, len(lst))):
    for j in range(min(K, len(C))):
        ans += [lst[i]+C[j]]

ans.sort(reverse = True)
for i in range(K):
    print (ans[i])
### BUGGY CODE ###

N = int(input())
Match = [0] * N
mod = 10**9 + 7
for i in range(N):
    A = list(map(int, input().split()))
    m = 0
    for j, a in enumerate(A):
        if a:
            m |= (1 << j)
    Match[i] = m

DP = [0] * (1 << N)
DP[0] = 1

for m in Match:
    D = DP[:]
    for i, d in enumerate(DP):
        if d:
            for j in range(N):
                if (m >> j) & 1 == 1:
                    if (i >> j) & 1 == 0:
                        D[i| (1 << j)] += d
                        D[i| (1 << j)] %= mod
    DP = D
print(DP[-1] % mod)

### FIXED CODE ###

N = int(input())
Match = [0] * N
mod = 10**9 + 7
for i in range(N):
    A = list(map(int, input().split()))
    m = 0
    for j, a in enumerate(A):
        if a:
            m |= (1 << j)
    Match[i] = m

DP = [0] * (1 << N)
DP[0] = 1

bit_count = [0]
for _ in range(N):
    bit_count += [x+1 for x in bit_count]

for i in range((1 << N) - 1):
    c = bit_count[i]
    if DP[i] == 0:
        continue
    for j in range(N):
        if (Match[c] >> j) & 1 == 1:
            if (i >> j) & 1 == 0:
                DP[i| (1 << j)] += DP[i]
                DP[i| (1 << j)] %= mod
print(DP[-1] % mod)
### BUGGY CODE ###

K, S = map(int, input().split())
ans = 0
for x in range(K+1):
    if S - x > 2 * K:
        continue
    for y in range(K+1):
        z = S - x - y
        if 0 <= z <= K and x + y + z == S:
            ans += 1
print(ans)


### FIXED CODE ###

from itertools import  product
K, S = map(int, input().split())
ans = 0
for x,y in product(range(K+1),repeat=2):
    z = S - x - y
    if 0 <= z <= K and x + y + z == S:
        ans += 1
print(ans)
### BUGGY CODE ###

q = int(input().rstrip())
for i in range(q):
    x = input().rstrip()
    y = input().rstrip()
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    print(dp1[-1])


### FIXED CODE ###

def calc(x,y):
    n = len(x)
    m = len(y)
    dp1 = [0]*(m+1)
    for i in range(n):
        s = x[i]
        dp2 = dp1[:]
        for j in range(m):
            if s == y[j]:
                dp1[j+1] = dp2[j]+1
            elif dp1[j+1] < dp1[j]:
                dp1[j+1] = dp1[j]
    return dp1[-1]

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(calc(x,y))
### BUGGY CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
r = [[0] * n for _ in range(n)]

p = [0] * n

for i in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    p[a] = max(p[a], h[b])
    p[b] = max(p[b], h[a])

ans = 0
for i in range(n):
    if h[i] > p[i]:
        ans += 1

# print(p)
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
 
edeg = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    edeg[a].append(b)
    edeg[b].append(a)
 
#print(edeg)

ans = 0
for node in range(n):
    good = True
    for neigber in edeg[node]:
        #print("neigber:", neigber)
        if h[node] <= h[neigber]:
            good = False
    if good:
        ans += 1 

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

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split())) + [10 ** 10]
a.sort()

def check(x):
  dp = [0] * (K + 1)
  dp[0] = 1
  for i in range(N):
    for j in range(K - 1, -1, -1):
      if i == x: continue
      if dp[j]:
        dp[min(K, j + a[i])] = dp[j]
  for j in range(max(0, K - a[x]), K):
    if dp[j]: return True
  return False
#for i in range(N): print(check(i))

if check(0):
  print(0)
  exit(0)
ok = N + 1
ng = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m
print(ok)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
t = 0
res = -1
for i in range(N):
  if t + a[i] < K: t += a[i]
  else: res = i
print(N - res - 1)
### BUGGY CODE ###

def resolve():
    N = int(input())
    S = []
    for _ in range(N):
        s = input()
        S.append(s)
    SS = sorted(list(set(S)))
    ans = []
    for i in SS:
        ans.append(S.count(i))
    ooki = max(ans)
    for j in range(len(SS)):
        if ans[j] == ooki:
            print(SS[j])
resolve()

### FIXED CODE ###

count = {}
for i in range(int(input())):
    S = input()
    if S in count:
        count[S] += 1
    else:
        count[S] = 1
ans = max(count.values())
print(*sorted([A[0] for A in count.items() if A[1] == ans]))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(lambda x:int(x)%k, input().split()))
for i in range(1,n):
  a[i] += a[i-1]
b = 0
for j in range(n):
  if a[j]%k == j+1:
    b += 1
  for i in range(max(0,j-k+1),j):
    if (a[j]-a[i])%k == j-i:
      b += 1
print(b)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
a[0] = (a[0]-1)%k
for i in range(1,n):
  a[i] = (a[i]+a[i-1]-1)%k
ans = 0
b = {0:1}
for i in range(n):
  if i>0:
    b[a[i-1]] = b.get(a[i-1],0) + 1
  if i>=k:
    b[a[i-k]] -= 1
  if i==k-1:
    b[0] -= 1
  ans += b.get(a[i],0)
print(ans)
### BUGGY CODE ###

import numpy as np

l, r = map(int, input().split())

m = 2019
mod_min = []

input_list = [i for i in range(l,r+1,1)]
input_list = np.asarray(input_list)

input_list = input_list % 2019
#print(input_list)

for i in range(len(input_list)):
    for j in range(len(input_list)-1, i, -1):
        mod_min.append((input_list[i] * input_list[j]) % m)

#print(mod_min)
print(np.asarray(mod_min).min())

### FIXED CODE ###

l, r = map(int, input().split())

m = 2019
mod_min = m

is_return = False

for j in range(l,r+1,1):
    #j_ = j % m
    #if j_ == 0:
        #break
        
    if is_return:
        break
    for i in range(l,j,1):
        #i_ = i % m
        i_j = (i * j) % m
        
        if i_j < mod_min:
            mod_min = i_j
            
        if i_j == 0:
            is_return = True
            break
            
print(mod_min)
### BUGGY CODE ###

N, K = map(int, input().split())
*H, = map(int, input().split())
INF = 10**12
dp = {i: INF for i in range(N+1)}
dp[0] = 0
dp[1] = abs(H[1] - H[0])
for i in range(2, N):
    for j in range(1, K+1):
        if i >= j:
            dp[i] = min(dp[i], dp[i-j] + abs(H[i] - H[i-j]))
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
*H, = map(int, input().split())
INF = 10**12
dp = [INF]*N
dp[0] = 0
dp[1] = abs(H[1] - H[0])
for i in range(2, N):
    beg = min(i, K)
    h_now = H[i]
    dp[i] = min([d + abs(h_now - h) for d, h in zip(dp[i-beg:i], H[i-beg:i])])
print(dp[N-1])
### BUGGY CODE ###

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
for i in range(H):
    B=list(map(int,input().split()))
    for j in range(W):
        A[i][j]=abs(A[i][j]-B[j])
dp=[[set() for i in range(W)] for i in range(H)]
dp[0][0].add(A[0][0])
for i in range(H):
    for j in range(W):
        for nx,ny in [(i+1,j),(i,j+1)]:
            if nx>=H or ny>=W:
                continue
            for k in dp[i][j]:
                p=k+A[nx][ny]
                m=abs(k-A[nx][ny])
                dp[nx][ny].add(p)
                dp[nx][ny].add(m)
ans=10**18
for k in dp[H-1][W-1]:
    ans=min(ans,k)
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
for i in range(H):
    B=list(map(int,input().split()))
    for j in range(W):
        A[i][j]=abs(A[i][j]-B[j])
D=80*(H+W)+1
D2=D*2
dp=[[0]*W for i in range(H)]
dp[0][0]|=1<<(D+A[0][0])
dp[0][0]|=1<<(D-A[0][0])
for i in range(H):
    for j in range(W):
        if i:
            dp[i][j]|=dp[i-1][j]<<A[i][j]
            dp[i][j]|=dp[i-1][j]>>A[i][j]
        if j:
            dp[i][j]|=dp[i][j-1]<<A[i][j]
            dp[i][j]|=dp[i][j-1]>>A[i][j]
res=dp[-1][-1]
ans=10**18
for i in range(D2):
    if res>>i&1:
        ans=min(ans,abs(D-i))
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

H, W = map(int, input().split(" "))
s = [list(input()) for _ in range(0, H)]

d = {}
def walk(i, j, c):
	if i < 0 or i >= H or j < 0 or j >= W:
		return
	if s[i][j] != ".":
		return
	if (i, j) in d and c >= d[(i, j)]:
		return

	d[(i, j)] = c
	for z in range(i-1, i+2):
		walk(z, j, c+1)
	for z in range(j-1, j+2):
		walk(i, z, c+1)

walk(0, 0, 1)
if (H-1, W-1) in d:
	print("".join(map(lambda x: "".join(x), s)).count(".") - d[(H-1, W-1)])
else:
	print(-1)


### FIXED CODE ###

INF=10*10
H,W=map(int, input().split())
s=[list(input()) for _ in range(H)]
wall=sum(map(lambda x: x.count("#"), s))
d=[[INF for _ in range(W)] for _ in range(H)]
def bfs(h, w, c):
	if d[h][w] <= c:
		return
	d[h][w] = c
	for dh,dw in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
		if h+dh >= 0 and w+dw >= 0 and h+dh < H and w+dw < W and s[h+dh][w+dw] == ".":
			bfs(h+dh, w+dw, c+1)
bfs(0, 0, 1)
print(-1 if d[H-1][W-1] == INF else H*W - d[H-1][W-1] - wall)
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 0

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        if s[j] == s[i]:
            continue
        for k in range(j + 1, n):
            if s[k] == s[i] or s[k] == s[j] or 2 * j - i == k:
                continue

            ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = list(input())
r = 0
g = 0
b = 0


for i in range(n):
    if s[i] == 'R':
        r += 1
    elif s[i] == 'G':
        g += 1
    else:
        b += 1

ans = r * g * b

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        k = 2 * j - i
        if k < n:
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                ans -= 1


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

from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'


n,m=MI()
ans=(n+m)//2 if (n-m)%2==0 else imp
for n in range(n):
    0

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
from collections import deque
import itertools
from itertools import permutations
import sys
import bisect
sys.setrecursionlimit(10**6)
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
YNeos='YNeos'
mo=10**9+7
imp='IMPOSSIBLE'


n,m=MI()
ans=(n+m)//2 if (n-m)%2==0 else imp

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

from collections import Counter

def resolve():
  N = int(input())
  countA = Counter([int(x) for x in input().split(" ")])
  Q = int(input())

  sum_A = 0
  for a in countA.items():
    sum_A += a[0]*a[1]

  for _ in range(Q):
    B, C = map(int, input().split(" "))
    if B in countA.keys():
      countA[C] += countA.pop(B)
      sum_A = 0
      for a in countA.items():
        sum_A += a[0]*a[1]
      print(sum_A)
    else:
      print(sum_A)


if __name__ == "__main__":
  resolve()


### FIXED CODE ###

from collections import Counter

def resolve():
  N = int(input())
  countA = Counter([int(x) for x in input().split(" ")])
  Q = int(input())

  sum_A = 0
  for a in countA.keys():
    sum_A += a*countA[a]

  for _ in range(Q):
    B, C = map(int, input().split(" "))
    if B in countA.keys():
      target_value = countA.pop(B)
      sum_A += (C - B) * target_value
      countA[C] += target_value
      print(sum_A)
    else:
      print(sum_A)


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

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = []
        for i in range(n):
            self.d.append([1e100]*n)
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d

n,m,l = map(int,input().split())
wf = WarshallFloyd(n)
for i in range(m):
    a,b,c = map(int,input().split())
    wf.path(a-1,b-1,c)
d = wf.build()
wf = WarshallFloyd(n)

for i in range(1,n):
    for j in range(i):
        if d[i][j] <= l:
            wf.path(i,j,1)

ans = wf.build()

q = int(input())
for i in range(q):
    s,t = map(int,input().split())
    if ans[s-1][t-1] == 1e100:
        print(-1)
    else:
        print(ans[s-1][t-1] - 1)


### FIXED CODE ###

import sys
input = sys.stdin.readline

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = []
        for i in range(n):
            self.d.append([1e100]*n)
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d

n,m,l = map(int,input().split())
wf = WarshallFloyd(n)
for i in range(m):
    a,b,c = map(int,input().split())
    wf.path(a-1,b-1,c)
d = wf.build()

wf = WarshallFloyd(n)
for i in range(1,n):
    for j in range(i):
        if d[i][j] <= l:
            wf.path(i,j,1)

ans = wf.build()

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

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = LI()
h = []
for i in s:
    heappush(h,-i)
x = heappop(h)
use = [-x]
for _ in range(n):
    use_tmp = []
    for i in use:
        rest_tmp = []
        while h:
            x = heappop(h)
            x = -x
            if i > x:
                use_tmp.append(x)
                break
            else:
                rest_tmp.append(x)
        for j in rest_tmp:
            heappush(h,-j)
    use += use_tmp
if len(use) == 2**n:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = LI()
s.sort(reverse=True)
use = [s[0]]
rest = s[1:]
for _ in range(n):
    new_use = []
    que = deque(rest)
    for i in use:
        rest_tmp = []
        while que:
            x = que.popleft()
            if i > x:
                new_use.append(x)
                break
            else:
                rest_tmp.append(x)
        que += rest_tmp
    use += new_use
    use.sort(reverse=True)
    rest = list(que)
    rest.sort(reverse=True)
if len(use) == 2**n:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
tf=[1]*n
n=n-1
notdiv=True
firstyn=0
for i in range(n,-1,-1):
  notdiv=True
  for j in range(i):
    if a[i]%a[j] == 0:
      tf[i]=0
    if a[j]%a[i] == 0:
      tf[j]=0
print(sum(tf))

### FIXED CODE ###

def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]+1
  tf=[False]*maxa
  r=0
  n-=1
  for i in range(n):
    a_i=a[i]
    if tf[a_i] ==False:
      for j in range(a_i,maxa,a_i):
        tf[j]=True
      if a_i < a[i+1]:
        #print(a_i)
        r+=1
  if tf[-1] ==False:
    r+=1
  print(r)
main()
### BUGGY CODE ###

def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        k = int(k)
        ndp = [0] * d

        for di, dk in enumerate(dp):
            for ndi in range(di, di + 10):
                ndp[ndi % d] += dk

        for ndi in range(just, just + k):
            ndp[ndi % d] += 1

        for dk in dp:
            dk %= md

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = input()
d = int(input())
f(ks, d)


### FIXED CODE ###

def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        ndp = [0] * d

        for di, dk in enumerate(dp):
            for ndi in range(di, di + 10):
                ndp[ndi % d] += dk

        for ndi in range(just, just + k):
            ndp[ndi % d] += 1

        ndp = [ndk % md for ndk in ndp]

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = list(map(int, list(input())))
d = int(input())
f(ks, d)