Harryxun/stf_run huggingface dataset:
from heapq import heappush, heappop

# input
N,M =map(int,input().split())
A = [0]*N
B = [0]*M
C = [0]*M

A = list(map(int, input().split()))
A.sort()
for i in range(M):
    B[i],C[i] = list(map(int,input().split()))


def solve():

    pairs = zip(C, B)
    sortedpairs = sorted(pairs, key=lambda x: x[0])
    for i in range(M):
        B[i]=sortedpairs[i][1]
        C[i]=sortedpairs[i][0]

    ansA=[0]*N
    for j in range(N):
        ansA[j] = A[j]
    p = int(0)
    j = int(0)
    while  j<N :
        jd = int(0)
        while  B[M-1-p]-jd>0 :
            if ansA[j]>=C[M-1-p] :
                break
            ansA[j]=C[M-1-p]
            jd +=1
            j +=1
            if j==N : break
        if ansA[j] >= C[M - 1 - p]:
            break
        p +=1

    ans = int(0)
    for j in range(N):
        ans += ansA[j]

    print(ans)

solve()



### FIXED CODE ###

from heapq import heappush, heappop

# input
N,M =map(int,input().split())
A = [0]*N
B = [0]*M
C = [0]*M

A = list(map(int, input().split()))
A.sort()
for i in range(M):
    B[i],C[i] = list(map(int,input().split()))


def solve():

    pairs = zip(C, B)
    sortedpairs = sorted(pairs, key=lambda x: x[0])
    for i in range(M):
        B[i]=sortedpairs[i][1]
        C[i]=sortedpairs[i][0]

    ansA=[0]*N
    for j in range(N):
        ansA[j] = A[j]

    p = int(0)
    j = int(0)
    while  j<N and M>=1+p :
        jd = int(0)
        if ansA[j] >= C[M - 1 - p]:
            break
        while  B[M-1-p]-jd>0 :
            if j==N : break
            if ansA[j]>=C[M-1-p] :
                break
            else:
                ansA[j]=C[M-1-p]
            jd +=1
            j +=1

        p +=1

    ans = int(0)
    for j in range(N):
        ans += ansA[j]

    print(ans)

solve()
N=input()
lenN=len(N)
N=int(N)


if N%2==1 or N<10:
    print(0)
else:
    count=0
    loop=0
    while(1):
        if N<(10*5**loop) or N%(10*5**loop)!=0:
            break
        else:
            count+=N//(10*5**loop)
            loop+=1
print(count)

### FIXED CODE ###

N=input()
lenN=len(N)
N=int(N)




if N%2==1 or N<10:
    print(0)
else:
    count=0
    loop=0
    while(1):
        if N<(10*5**loop):
            break
        else:
            count+=N//(10*5**loop)
            loop+=1
    print(count)
a, b = map(int, input().split())

for i in range(10):
  c = (a * i) - (i - 1)
  if c >= b:
    ans = i
    break
  
print(ans)

### FIXED CODE ###

a, b = map(int, input().split())
ans = 0

for i in range(20):
  c = (a * i) - (i - 1)
  if c >= b:
    ans = i
    break
  
print(ans)
N=int(input())
N=[0]*(N+1)
for i in range(1,N):
  for j in range(i+1,N+1):
    m=min(j-i,abs(Y-j)+abs(X-i)+1)
    N[m]+=1
for k in range(1,N):
  print(A[k])


### FIXED CODE ###

N,X,Y=map(int,input().split())
A=[0]*(N+1)
for i in range(1,N):
  for j in range(i+1,N+1):
    m=min(j-i,abs(Y-j)+abs(X-i)+1)
    A[m]+=1
for k in range(1,N):
  print(A[k])
s = input()

for i in range(0, 9, 2):
    if i == 8 and len(s) <= 8:
        s = s[:i] + "A" + s[i:]
    elif i != 2:
        if s[i] != "A":
            s = s[:i] + "A" + s[i:]
if s == "AKIHABARA":
    print("YES")
else:
    print("NO")

### FIXED CODE ###

s = input()

if len(s) < 5:
    print("NO")
    exit()

for i in range(0, 9, 2):
    if i == 8 and len(s) <= 8:
        s = s[:i] + "A" + s[i:]
    elif i != 2:
        if s[i] != "A":
            s = s[:i] + "A" + s[i:]
if s == "AKIHABARA":
    print("YES")
else:
    print("NO")
a = input()
b = int(a)

s = (9-len(a))*'0'+a
ans = 0
for i in range(9):
    if s[i] == '0' and ans==0:
        continue
    ans+=(b//((10**(8-i))*10))*(10**(8-i))
    c = (b%((10**(8-i))*10))+1
    #print(0,c)
    if 2*(10**(8-i))>= c > 10**(8-i):
        ans+=c-10**(8-i)
    elif c>=2*10**((8-i)):
        ans+=10**(8-i)
    #print(ans)
print(ans)


### FIXED CODE ###

def lma():return list(map(int, input().split()))#x or y
a = lma()
f = 1
c =0
while f:
    if a[0]%2==1 or a[1]%2==1 or a[2]%2 ==1:break
    if (a[0] == a[1] and a[0] == a[2]) :
        c=-1
        break
    a[0],a[1],a[2] = (a[1]+a[2])/2,(a[0]+a[2])/2,(a[1]+a[0])/2
    c+=1
print(c)
predict = input()
actual  = input()

a = 0
for i in range(3):
	if(predict[i] == actual[i]):
    	a = a + 1
print(a)

### FIXED CODE ###

predict, actual = input(),input()
a = 0
for i in range(3):
    if(predict[i] == actual[i]):
        a = a + 1
print(a)
import Sample Input
S, s = Sample Input
a = int(h = (S / 3600) += m = ((S % 3600) / 60) += for s in range(0, 60): .split )
print('a')

### FIXED CODE ###

S = int(input())

s = S % 60
m = S // 60 % 60
h = S // 60 // 60

print("{0}:{1}:{2}".format(h,m,s))
s = input()

subsg = []
subsp = []

sg = 0
sp = 0
ans = 0
for i in range(N):
    if s[i] == 'g':
        sg += 1
    else:
        sp += 1
    subsg.append(sg)
    subsp.append(sp)

for i in range(N):
    if subsp <= subsg:
        ans += 1
    
print(ans)

### FIXED CODE ###

s = input()

sg = 0
sp = 0
ans = 0

for i in range(len(s)):
    if sp+1 <= sg and s[i] == 'g':
        sp += 1
        ans += 1
    elif sp+1 > sg and s[i] == 'p':
        sg += 1
        ans -= 1
    elif sp+1 <= sg and s[i] == 'p':
        sp += 1
    else:
        sg += 1
print(ans)
import math
def lcm(a,b):
    return (a*b) // math.gcd(a,b)
n = int(input())
t = []
for i in range(n):
    a = int(input())
    t.append(a)
b = t[0]
for i in range(1,n):
    b = lcm(b,t[i])
print(b)

### FIXED CODE ###

def gcd(a,b):
    return gcd(b,a % b) if b else abs(a)
def lcm(a,b):
    return (a*b) // gcd(a,b)
n = int(input())
t = []
for i in range(n):
    a = int(input())
    t.append(a)
b = t[0]
for i in range(1,n):
    b = lcm(b,t[i])
print(b)
A, B, C = [int(x) for x in input().split()]
print(max(A, B, C)　*　(２ **int(input())) + sum(A, B, C) - max(A, B, C))

### FIXED CODE ###

A, B, C = [int(x) for x in input().split()]
print(max(A, B, C) * (2 ** int(input())) + sum([A, B, C]) - max(A, B, C))
a, b, c = map(int, input().split())
k = int(input())

while k > 0:
  if b <= a:
    b *= 2
    k -= 1
  else:
    break
if k > 0:
  multiplier = 2 ** k
  if c * multiplier > b:
    ans = 'Yes'
  else:
    ans = 'No'

print(ans)


### FIXED CODE ###

a, b, c = map(int, input().split())
k = int(input())

if b > a:
  multiplier = 2 ** k
  if c * multiplier > b:
    ans = 'Yes'
  else:
    ans = 'No'
else:
  while b <= a:
    b *= 2
    k -= 1
  multiplier = 2 ** k
  if c * multiplier > b:
    ans = 'Yes'
  else:
    ans = 'No'

print(ans)
a,b=map(int,input().split())
count=0
for i in range(a,b+1):
    if str(i)　==　str(i)[::-1]:
        count+=1　#count++はダメ
       
print(count)


### FIXED CODE ###

a,b=map(int,input().split())
cnt = 0
for i in range(a, b+1):
	if str(i) == str(i)[::-1]:
		cnt += 1
 
print(cnt)
N,D=map(int,input().split())
l=[]
l1=[]
count=0
for i in range(N):
  x,y=map(int,input().split())
  l.append(x)
  l1append(y)
for i in range(N):
  if (l[i]**2 +l1[i]**2)**0.5 <=D:
    count+=1
print(count)    
  


### FIXED CODE ###

N,D=map(int,input().split())
l=[]
l1=[]
count=0
for i in range(N):
  x,y=map(int,input().split())
  l.append(x)
  l1.append(y)
for i in range(N):
  if (l[i]**2 +l1[i]**2)**0.5 <=D:
    count+=1
print(count)
N = int(input())
ai_list = list(map(int, input().split()))

import math
from statistics import mean, median
mean_ai = mean(ai_list)
median_ai = median(ai_list)
mean_lo = math.floor(mean_ai)
mean_high = math.ceil(mean_ai)

ans_list = []
cost1 = 0
cost2 = 0
cost3 = 0
for n in ai_list:
  cost1 += (n - mean_lo)**2
  cost2 += (n - mean_high)**2
  cost3 += (n - median_ai)**2
ans_list.append(cost1)
ans_list.append(cost2)
ans_list.append(cost3)
print(min(ans_list))

### FIXED CODE ###

N = int(input())
counter = 0
for i in range(1, N+1):
  counter += i
print(counter)
n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
sat=sum(b)
for i in range(n-1):
  if a[i+1]==a[i]+1:
    sat+=c[a[i]]
print(sat)


### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
sat=sum(b)
for i in range(n-1):
  if a[i+1]==a[i]+1:
    sat+=c[a[i]-1]
print(sat)
A = int(input())
B = int(input())
X = A + B
Y = A - B
Z = A * B

chinchin = [X, Y, Z]
print(max(chinchin))

### FIXED CODE ###


S = input().split()
X = int(S[0])+int(S[1])
Y = int(S[0])-int(S[1])
Z = int(S[0])*int(S[1])
if X >= Y:
    if X >= Z:
        print(X)
    else:
        print(Z)
else:
    if Y >= Z:
        print(Y)
    else:
        print(Z)
N = int(input())
ans = int(input())

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def lcm(x,y):
    return (int(x*y/gcd(x,y)))

for i in range(N-1):
    t = int(input())
    ans = lcm(ans,t)

print(ans)

### FIXED CODE ###

N = int(input())
ans = int(input())

def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

def lcm(x,y):
    return (x*y//gcd(x,y))

for i in range(N-1):
    t = int(input())
    ans = lcm(ans,t)

print(ans)
while 1:
	h,w = map(int,raw_input().split())
	if h == 0 and w == 0:
		break
	for number in range(h):
		print "#"*w /n

### FIXED CODE ###

while 1:
	h,w = map(int,raw_input().split())
	if h == 0 and w == 0:
		break
	for number in range(h):
		print "#"*w
	print ""
n, k, x, y = map(int, input().split('\n'))
basic = min(k * x, n * x)
plus = max((n - k) * y, 0)
print(basic + plus)

### FIXED CODE ###

n, k, x, y = [int(input()) for i in range(4)]
basic = min(k * x, n * x)
plus = max((n - k) * y, 0)
print(basic + plus)
s = list(input())
t = list(input())

cnt = 0
for i in range(2)
    if s[i]==s[t]:
        cnt =+1
print(cnt)

### FIXED CODE ###

s = list(input())
t = list(input())

cnt = 0
for i in range(len(s)):
    if s[i] == t[i]:
        cnt += 1
        continue
print(cnt)
s = str(input())

if s[0] == s[1]:
    if s[2] == s[3] and s[0] != s[2]:
        print('Yes')
    else:
        print('No')
elif s[0] == s[2]:
    if s[1] == s[3] and s[0] != s[1]:
        print('Yes')
    else:
        print('No')
elif s[0] == s[3]:
    if s[1] == s[2] and s[0] != s[1]:
        print('Yes')
        else:
        print('No')
else:
    print('No')

### FIXED CODE ###

s = str(input())

if s[0] == s[1]:
    if s[2] == s[3] and s[0] != s[2]:
        print('Yes')
    else:
        print('No')
elif s[0] == s[2]:
    if s[1] == s[3] and s[0] != s[1]:
        print('Yes')
    else:
        print('No')
elif s[0] == s[3]:
    if s[1] == s[2] and s[0] != s[1]:
        print('Yes')
    else:
        print('No')
else:
    print('No')
N, M, P = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

edges = [[] for _ in range(N)]
to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]

for a, b, c in X:
    a -= 1
    b -= 1
    c = -(c - P)
    edges[a].append((b, c))
    to[a].append(b)
    ot[b].append(a)

ok_1 = [False] * N
ok_n = [False] * N

# Reachable
def dfs(u):
    if ok_1[u]:
        return
    
    ok_1[u] = True
    for v in to[u]:
        dfs(v)
        
def rdfs(u):
    if ok_n[u]:
        return
    
    ok_n[u] = True
    for v in ot[u]:
        rdfs(v)
        
dfs(0)
rdfs(N - 1)
flag = [ok_1[i] & ok_n[i] for i in range(N)]

# Bellman ford
INF = 10 ** 9 + 7
d = [INF] * N
d[0] = 0
cnt = 0
updated = True
while updated and cnt <= N:
    updated = False
    cnt += 1
    for u in range(N):
        if not flag[u]:
            continue
        for v, c in edges[u]:
            if not flag[v]:
                continue

            value = d[u] + c
            if d[v] > d[u] + c:
                d[v] = value
                updated = True

if cnt > N:
    print(-1)
else:
    print(max(0, -d[-1]))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

N, M, P = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

edges = [[] for _ in range(N)]
to = [[] for _ in range(N)]
ot = [[] for _ in range(N)]

for a, b, c in X:
    a -= 1
    b -= 1
    c = -(c - P)
    edges[a].append((b, c))
    to[a].append(b)
    ot[b].append(a)

ok_1 = [False] * N
ok_n = [False] * N

# Reachable
def dfs(u):
    if ok_1[u]:
        return
    
    ok_1[u] = True
    for v in to[u]:
        dfs(v)
        
def rdfs(u):
    if ok_n[u]:
        return
    
    ok_n[u] = True
    for v in ot[u]:
        rdfs(v)
        
dfs(0)
rdfs(N - 1)
flag = [ok_1[i] & ok_n[i] for i in range(N)]

# Bellman ford
INF = 10 ** 9 + 7
d = [INF] * N
d[0] = 0
cnt = 0
updated = True
while updated and cnt <= N:
    updated = False
    cnt += 1
    for u in range(N):
        if not flag[u]:
            continue
        for v, c in edges[u]:
            if not flag[v]:
                continue

            value = d[u] + c
            if d[v] > d[u] + c:
                d[v] = value
                updated = True

if cnt > N:
    print(-1)
else:
    print(max(0, -d[-1]))
S=input()
if S="Sunny":
  print("Cloudy")
elif S="Cloudy":
  print("Rainy")
else:
  print("Sunny")

### FIXED CODE ###

S=input()
if S=="Sunny":
  print("Cloudy")
elif S=="Cloudy":
  print("Rainy")
else:
  print("Sunny")
num = input()
value = [int(n) for n in input().split()]
cost = [int(n) for n in input().split()]

ans=0
for i in range(num):
  if value[i] > cost[i]:
    ans = ans + value[i] - cost[i]

print(ans)

### FIXED CODE ###

num = int(input())
value = list(map(int, input().split()))
cost = list(map(int, input().split()))
ans = 0
for i in range(num):
  if value[i] > cost[i]:
    ans = ans + value[i] - cost[i]
 
print(ans)
n, w = [int(x) for x in input().split()]
W = []
V = []
for i in range(n):
  wi, vi = [int(x) for x in input().split()]
  W.append(wi)
  V.append(vi)
 
dp = []
for i in range(n+1):
  dp.append([0]*(w+1))
 
for i in range(n):
  for sum_w in range(w + 1):
    # 選ぶ場合
    if sum_w - W[i] >= 0:
      dp[i+1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w - W[i]] + V[i])
 
    # 選ばない場合
    dp[i+1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
 
print(dp[n][w])

### FIXED CODE ###

N, W = [int(x) for x in input().split()]

w, v = [], []
MAX_V = 100001
INF = 1000000000001

for i in range(N):
  wi, vi = [int(x) for x in input().split()]
  w.append(wi)
  v.append(vi)

dp = []
for i in range(N+1):
  dp.append([INF] * MAX_V)

dp[0][0] = 0

for i in range(N):
  for sum_v in range(MAX_V):
    if sum_v - v[i] >= 0:
      dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
      
    dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


res = 0
for sum_v in range(MAX_V):
  if dp[N][sum_v] <= W:
    res = sum_v
  
print(res)
from collections import deque

h,w = map(int,input().split())
A = [input() for i in range(h)]

queue = deque([])
Distance = [[-1 for i in range(w)]for j in range(h)]

for i in range(h):
  for j in range(w):
    if A[i][j]=='#':
      queue.append([i,j])
      Distance[i][j] = 0

while queue:
    x,y = queue.popleft()
    if x!=0:
        if A[x-1][y] == '.' and Distance[x-1][y] == -1:
            queue.append([x-1,y])
            ans = Distance[x-1][y] = Distance[x][y] + 1
    if x!=h-1:
        if A[x+1][y] == '.' and Distance[x+1][y] == -1:
            queue.append([x+1,y])
            ans = Distance[x+1][y] = Distance[x][y] + 1
    if y!=0:
        if A[x][y-1] == '.' and Distance[x][y-1] == -1:
            queue.append([x,y-1])
            ans = Distance[x][y-1] = Distance[x][y] + 1
    if y!=w-1:
        if A[x][y+1] == '.' and Distance[x][y+1] == -1:
            queue.append([x,y+1])
            ans = Distance[x][y+1] = Distance[x][y] + 1

print(ans)

### FIXED CODE ###

def main():
    from collections import deque

    h,w = map(int,input().split())
    A = []
    for i in range(h):
        A += list(input())

    queue = deque([])
    Distance = [-1]*(h*w)

    for i in range(h):
        for j in range(w):
            if A[i*w+j]=='#':
                queue.append([i,j])
                Distance[i*w+j] = 0

    ans = 0

    while queue:
        x,y = queue.popleft()
        d = Distance[x*w+y]
        if x!=0 and Distance[(x-1)*w+y] == -1:
                queue.append([x-1,y])
                ans = Distance[(x-1)*w+y] = d+1
        if x!=h-1 and Distance[(x+1)*w+y] == -1:
                queue.append([x+1,y])
                ans = Distance[(x+1)*w+y] = d+1
        if y!=0 and Distance[x*w+y-1] == -1:
                queue.append([x,y-1])
                ans = Distance[x*w+y-1] = d+1
        if y!=w-1 and Distance[x*w+y+1] == -1:
                queue.append([x,y+1])
                ans = Distance[x*w+y+1] = d+1

    print(ans)
if __name__ == '__main__':
    main()
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
uv=[list(map(int,input().split())) for i in range(n-1)]
edge=defaultdict(list)
for i in range(n-1):
    u,v=uv[i]
    edge[u].append(v)
    edge[v].append(u)
# print(edge)

itta=[0]*(n+1)
# lislist=[0]*(n+1)

def dfs(now,lis):
    stk=0
    if a[now-1]>lis[-1]:
        lis.append(a[now-1])
        stk="pop"
    else:
        tmp=bisect.bisect_left(lis, a[now-1])
        stk=[tmp,lis[tmp]]
        lis[tmp]=a[now-1]
    
    # print(now,lis)
    itta[now]=len(lis)
    for i in edge[now]:
        if itta[i]==0:
            dfs(i,lis)
    
    if stk=="pop":
        lis.pop()
    else:
        lis[stk[0]]=stk[1]

dfs(1,[float('inf')])

# print(itta)
for i in range(n):
    print(itta[i+1])

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(1000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
uv=[list(map(int,input().split())) for i in range(n-1)]
edge=defaultdict(list)
for i in range(n-1):
    u,v=uv[i]
    edge[u].append(v)
    edge[v].append(u)
# print(edge)

itta=[0]*(n+1)
# lislist=[0]*(n+1)

def dfs(now,lis):
    stk=0
    if a[now-1]>lis[-1]:
        lis.append(a[now-1])
        stk="pop"
    else:
        tmp=bisect.bisect_left(lis, a[now-1])
        stk=[tmp,lis[tmp]]
        lis[tmp]=a[now-1]
    
    # print(now,lis)
    itta[now]=len(lis)
    for i in edge[now]:
        if itta[i]==0:
            dfs(i,lis)
    
    if stk=="pop":
        lis.pop()
    else:
        lis[stk[0]]=stk[1]

dfs(1,[float('inf')])

# print(itta)
for i in range(n):
    print(itta[i+1])
import sys
sys.setrecursionlimit(10**6)
N,M = map(int,input().split())
A = []
MOD = 10**9+7
memo = {}
for _ in range(M):
  memo[a] = 0

def step(cur):
  if cur in memo:
    return memo[cur]
  if cur == N:
    memo[cur] = 1
    return memo[cur]
  if cur > N:
    memo[cur] = 0
    return memo[cur]
 
  memo[cur] = (step(cur+1) + step(cur+2))%MOD
  return memo[cur]
 
print(step(0)%MOD)

### FIXED CODE ###

N,M = map(int,input().split())
MOD = 10**9+7
dp = [0] * (N+1)
dp[1] = 1
for _ in range(M):
  dp[int(input())] = -1
if N<2:
  print(dp[N])
  exit()

if dp[2] != -1:
  dp[2] = 1
for i in range(N+1):
  if dp[i] == -1: continue
  if i-1>=0 and dp[i-1] != -1:
    dp[i] += dp[i-1]
  if i-2>=0 and dp[i-2] != -1:
    dp[i] += dp[i-2]
  dp[i] %= MOD

print(dp[N])
from collections import Counter
n,p=map(int,input().split())
s=input()[::-1]
DP=[0]

if p==2 or p==5:
    if s[0]%p==0:print(n*(n+1)//2)
    else:print(0)
else:
    num,point=0,1
    for i in s:
        num +=int(i)*point
        num %=p
        DP.append(num)
        point *=10
        point %=p
    
    ans=0
    DP=Counter(DP)
    for v,m in DP.items():
        if m>=2:ans +=m*(m-1)//2
    print(ans)

### FIXED CODE ###

from collections import Counter
n,p=map(int,input().split())
s=input()
DP=[0]
ans=0

if p==2 or p==5:
    for i,j in enumerate(s):
        if int(j)%p==0:
            ans +=i+1
else:
    num,point=0,1
    for i in s[::-1]:
        num +=int(i)*point
        num %=p
        DP.append(num)
        point *=10
        point %=p

    DP=Counter(DP)
    for v,m in DP.items():
        if m>=2:ans +=m*(m-1)//2
print(ans)
import itertools
import math
n = int(input())
m = math.factorial(n)
l = [list(map(int,input().split())) for i in range(n)]
x,y = [list(i) for i in zip(*l)]
z = list(range(n))
z = list(itertools.permutations(l))
ans = 0
for i in range(m):
    for j in range(n-1):
        ans += math.sqrt((x[z[i][j]] - x[z[i][j+1]]) ** 2 + (y[z[i][j]] - y[z[i][j+1]]) ** 2)
print(ans / m)

### FIXED CODE ###

import itertools
import math
n = int(input())                    #n = 町の個数
l = [list(map(int,input().split())) for i in range(n)]
x,y = [list(i) for i in zip(*l)]    #x,y = 町の座標
l = list(range(n))                  
z = list(itertools.permutations(l)) #z = 経路の組み合わせ
m = math.factorial(n)               #m = 経路の個数
t = 0                               #t = 長さの合計

for i in range(m):
    for j in range(n - 1):
        t += math.sqrt((x[z[i][j]] - x[z[i][j+1]]) ** 2 + (y[z[i][j]] - y[z[i][j+1]]) ** 2)

print(t / m)
a,p=map(int,input().split())
_a=a*3
print(int(sum(_a+p)//2))

### FIXED CODE ###

a,p=map(int,input().split());print((a*3+p)//2)
clause_list = list(map(int, input().split()))

for index, clause in enumerate(clause_list):
  if clause = 5:
    clause_list.pop(index)
    break

for index, clause in enumerate(clause_list):
  if clause = 7:
    clause_list.pop(index)
    break

for index, clause in enumerate(clause_list):
  if clause = 5:
    clause_list.pop(index)
    break

print('YES' if len(clause_list) == 0 else 'NO')


### FIXED CODE ###

clause_list = list(map(int, input().split()))

for index, clause in enumerate(clause_list):
  if clause == 5:
    clause_list.pop(index)
    break

for index, clause in enumerate(clause_list):
  if clause == 7:
    clause_list.pop(index)
    break

for index, clause in enumerate(clause_list):
  if clause == 5:
    clause_list.pop(index)
    break

print('YES' if len(clause_list) == 0 else 'NO')
s=input();print("YNEOS"[15-len(s)+s.count("o")<8::2])'

### FIXED CODE ###

s=input();print("YNEOS"[15-len(s)+s.count("o")<8::2])
import sys

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

input = sys.stdin.readline
n,m = map(int, input().split())
A = list(map(int,input().split()))

for j in range(m):
    A.sort()
    b,c = map(int, input().split())
    if A[b] > c:
        for i in range(c):
            if A[0] < c-i:
                f = my_index(A, c-i)
                if f != -1:
                    A[:f]=[c]*f
                    break
            else:
                break
    else:
        A[:b]=[c]*b


print(sum(A))


### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline
n,m = map(int, input().split())
A = list(map(int,input().split()))
d = [list(map(int,input().split())) for _ in range(m)]

d.sort(key=lambda x:-x[1])
total = sum(A)
heapq.heapify(A)

for i in range(m):
    for j in range(d[i][0]):
        tmp = heapq.heappushpop(A, d[i][1])
        if tmp < d[i][1]:
                total += (d[i][1] - tmp)
        else:
            break

print(total)
import sys
import numpy as np

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.full((n+1, w+1), -1)

def rec(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == n:
    res = 0
  elif j == 0:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w+1) for _ in range(n+1)]

def rec(i, j):
  if dp[i][j] != 0:
    return dp[i][j]
  if i == n:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))