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

import sys

def input():
    return sys.stdin.readline().strip()

def main():

    N,M = map(int,input().split())
    A = sorted(list(map(int,input().split())))
    BC = [list(map(int,input().split())) for _ in range(M)]
    BC = sorted(BC,reverse=True,key=lambda x: x[1])
    D = []

    for B,C in BC:
        for b in range(B):
            D.append(C)

    for i in range(len(D)):
        if A[i] < D[i]:
            A[i] = D[i]
        else:
            break

    print(sum(A))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():

    N,M = map(int,input().split())
    A = sorted(list(map(int,input().split())))
    BC = [list(map(int,input().split())) for _ in range(M)]
    BC = sorted(BC,reverse=True,key=lambda x: x[1])
    D = []

    for B,C in BC:
        for b in range(B):
            if len(D) != N:
                D.append(C)
            else:
                break
        else:
            continue
        break

    for i in range(len(D)):
        if A[i] < D[i]:
            A[i] = D[i]
        else:
            break

    print(sum(A))

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

def main():
    N,W=map(int,input().split())
    dp=[[0]*(W+1) for _ in range(N+1)]
    for i in range(1,N+1):
        w,v=map(int,input().split())
        for j in range(W+1):
            if w<=j:
                can1=max(dp[i-1][k] for k in range(j-w+1))
                can2=max(dp[i-1][k] for k in range(j-w+1,j+1))
                dp[i][j]=max(can1+v,can2)
            else:
                dp[i][j]=dp[i-1][j]
    print(dp[N][W])
main()

### FIXED CODE ###

import numpy as np
N,W=map(int,input().split())
dp=np.zeros(W+1,dtype=int)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])
### BUGGY CODE ###

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

r = 0
for i in range(N - 1):
  for j in range(i+1, N):
    r += (A[i]) ^ (A[j])

print(r % (10**9 + 7))

### FIXED CODE ###

import numpy as np 
N = int(input())
A = np.fromstring(input(), dtype = np.int64, sep = ' ')

res = 0
for bit in range(60):
  c = int((A & 1).sum())
  res += c * (N - c) * (1 << bit)
  A >>= 1

print(res % 1000000007)
### BUGGY CODE ###

import heapq

N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A = [A[i] * (-1) for i in range(N)]
heapq.heapify(A)
heapq.heapify(F)
AF = []
for _ in range(N):
	t_a = heapq.heappop(A)
	t_f = heapq.heappop(F)
	AF.append([t_a*t_f, t_f])

heapq.heapify(AF)
for _ in range(K):
	t,f = heapq.heappop(AF)
	heapq.heappush(AF,[min(0,t+f), f])

ans, f = heapq.heappop(AF)
print(ans*(-1))

### FIXED CODE ###



N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort(reverse = True)
F.sort()

max_f = A[0] * F[-1]

def binary_search(min_f, max_f):
	if min_f == max_f:
		return min_f

	mid_f = min_f + (max_f - min_f)//2
	tmp = 0
	for i in range(N):
		tmp += max(0,A[i] - mid_f // F[i])
	
	if tmp <= K:
		return binary_search(min_f, mid_f)
	else:
		return binary_search(mid_f+1, max_f)

print(binary_search(0, max_f))
### BUGGY CODE ###

from collections import deque
N,M = map(int,input().split())
UV = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

es = [[set() for j in range(N)] for i in range(3)]
for u,v in UV:
    es[0][u].add(v)

nex = {}
for i in range(2):
    for j in range(N):
        if hash(str(es[i][j])) in nex:
            es[i+1][j] = nex[hash(str(es[i][j]))]
            continue
        for k in es[i][j]:
            es[i+1][j] |= es[0][k]
        nex[hash(str(es[i][j]))] = es[i+1][j]

INF = float('inf')
dist = [INF]*N
dist[S] = 0
q = deque([S])
while q:
    v = q.popleft()
    for to in es[2][v]:
        if dist[to] != INF: continue
        dist[to] = dist[v]+1
        if to == T:
            print(dist[to])
            exit()
        q.append(to)

print(-1)

### FIXED CODE ###

from collections import deque
import sys
inputs = sys.stdin.readline
N,M = map(int,input().split())
UV = [tuple(map(lambda x:int(x)-1,inputs().split())) for i in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

es = [[] for i in range(3*N)]
for u,v in UV:
    es[u].append(v+N)
    es[u+N].append(v+2*N)
    es[u+2*N].append(v)

q = deque([S])
INF = float('inf')
dist = [INF] * (3*N)
dist[S] = 0

while q:
    v = q.popleft()
    for to in es[v]:
        if dist[to] != INF: continue
        dist[to] = dist[v] + 1
        if to==T:
            print(dist[to] // 3)
            exit()
        q.append(to)
print(-1)
### BUGGY CODE ###

from collections import deque

class SlideMin:
    """
    スライド最小値\n
    各区間[ai, ai+leng]の最小値を取得する：O(n)\n
    self.que = [(i1, v1), (i2, v2), ..., (ik, vk)]\n
    i1 < ... < ik and v1 < ... < vk
    """
    def __init__(self, leng):
        self.que = deque([])
        self.leng = leng

    def top(self):
        return self.que[0]

    def getQue(self):
        return self.que

    def update(self, index, value):
        while self.que:
            if self.que[-1][1] >= value:
                self.que.pop()
            else:
                break

        self.que.append((index, value))

        if self.que[0][0] == index - self.leng:
            self.que.popleft()

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

def sol(n):
    # n個前までの最小値
    B = A + A
    que = SlideMin(n + 1)
    ret = [10**18] * N
    for i, a in enumerate(B):
        que.update(i, a)
        ret[i % N] = min(ret[i % N], que.top()[1])
    return sum(ret) + n * X

ans = sum(A)
for i in range(N):
    ans = min(ans, sol(i))
print(ans)


### FIXED CODE ###

import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def sol():
    N, X = map(int, input().split())
    A = list(map(int, input().split()))

    B = A.copy()
    ans = sum(B)
    for magic in range(1, N):
        for i in range(N):
            B[i] = min(B[i], A[i - magic])
        ans = min(ans, sum(B) + X * magic)

    print(ans)

sol()
### BUGGY CODE ###



def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    # dp[i] = min(abs(h[i]-h[i-1])+dp[i-1], abs(h[i]-h[i-2])+dp[i-2])
    N, K = read_ints()
    h = read_ints()
    dp = [0, abs(h[1]-h[0])]
    for i in range(2, N):
        dp.append(min(abs(h[i]-h[i-k])+dp[i-k] for k in range(1, K+1) if i >= k))
    return dp[-1]


if __name__ == '__main__':
    print(solve())


### FIXED CODE ###


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    # dp[i] = min(abs(h[i]-h[i-1])+dp[i-1], abs(h[i]-h[i-2])+dp[i-2])
    N, K = read_ints()
    h = read_ints()
    dp = [0, abs(h[1]-h[0])]
    for i in range(2, N):
        dp.append(min(abs(h[i]-h[i-k])+dp[i-k] for k in range(1, K+1) if i >= k))
    return dp[-1]


if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

s = input()
l1 = len(s)

for i in range(l1):
    if '01' in s:
        s = s.replace('01', '')
    elif '10' in s:
        s = s.replace('10', '')
    else:
        break
        
print(l1 - len(s))

### FIXED CODE ###

s = input()
cnt = [s.count('0'), s.count('1')]

print(len(s) - (max(cnt) - min(cnt)))
### BUGGY CODE ###

"""C."""

import sys

input = sys.stdin.readline  # noqa: A001

n = int(input())
a = list(map(int, input()[:-1].split(' ')))

MOD_VALUE = pow(10, 9) + 7
result = 0

for i in range(n - 1):
    for j in range(i + 1, n):
        result += a[i] * a[j]
print(result % MOD_VALUE)


### FIXED CODE ###

"""C."""

import sys

input = sys.stdin.readline  # noqa: A001

n = int(input())
a = list(map(int, input()[:-1].split(' ')))

MOD_VALUE = 10**9 + 7
result = 0

a_sum = sum(a)

for i, v in enumerate(a):
    result += v * (a_sum - v)
    a_sum -= v

if result < MOD_VALUE:
    print(result)
else:
    print(result % MOD_VALUE)
### BUGGY CODE ###

n = int(input())
p = 1
for i in range(1, n+1):
    p *= i
print(p%(10**9+7))

### FIXED CODE ###

import math
n = int(input())
power = math.factorial(n)
print(power%(10**9+7))
### BUGGY CODE ###

def main():
    from collections import deque
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = deque()
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.append([i,j])
                cnt += 1
    ans = 0
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt<h*w:
        ans += 1
        n = len(q)
        for _ in range(n):
            b = q.popleft()
            for nx in nxt:
                mv = [b[0]+nx[0],b[1]+nx[1]]
                if -1<mv[0]<h and -1<mv[1]<w:
                    if S[mv[0]][mv[1]]=='#':
                        continue
                    cnt += 1
                    S[mv[0]][mv[1]]='#'
                    q.append(mv)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

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

import sys

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = {}
for ln in range(n + 1):
  for rn in range(n + 1 - ln):
    if ln + rn > n or dp.get((ln, rn)):
      continue

    if ln == rn == 0:
      dp[0, 0] = 0
    else:
      p, a = arr[ln + rn - 1]
      val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
      val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

      dp[ln, rn] = max(val_l, val_r)

print(max([dp[i, n - i] for i in range(n + 1)]))


### FIXED CODE ###


def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()
### BUGGY CODE ###

n = int(input())
A = tuple(map(int, input().split()))
ans = 1
for a in A:
    ans *=a
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
A = tuple(map(int, input().split()))
ans = 1
if 0 in A:
    print(0)
    exit()
for a in A:
    ans *=a
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
hw = [list(input().strip()) for _ in range(H)]
b = deque()
for h in range(H):
    for w in range(W):
        if hw[h][w] == '#':
            b.append([h, w, 0])

ans = 0
while len(b) > 0:
    h, w, d = b.popleft()
    for y, x in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = h + y, w + x
        if nh >= 0 and nh < H and nw >= 0 and nw < W and hw[nh][nw] == '.':
            b.append([nh, nw, d + 1])
            ans = max([ans, d + 1])
            hw[nh][nw] = "#"
print(ans)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
hw = [list(input().strip()) for _ in range(H)]
b = deque()
for h in range(H):
    for w in range(W):
        if hw[h][w] == '#':
            b.append([h, w, 0])

ans = 0
while len(b) > 0:
    h, w, d = b.popleft()
    d += 1
    for y, x in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = h + y, w + x
        if nh >= 0 and nh < H and nw >= 0 and nw < W and hw[nh][nw] == '.':
            b.append([nh, nw, d])
            if ans < d:
                ans = d
            hw[nh][nw] = "#"
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
a=A[:]
for _ in range(K):
    t=[0]*(N+1)
    for i in range(N):
        ti=a[i]
        t[max(0,i-ti)]+=1
        t[min(N,i+ti+1)]-=1
    a=[]
    for i in range(N):
        a.append(t[i])
        if i>0:
            a[i]+=a[i-1]
print(*a)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
a=A[:]
for _ in range(K):
    t=[0]*(N+1)
    for i in range(N):
        ti=a[i]
        t[max(0,i-ti)]+=1
        t[min(N,i+ti+1)]-=1
    a=[]
    for i in range(N):
        a.append(t[i])
        if i>0:
            a[i]+=a[i-1]
    if min(a)==N:
        break
print(*a)
### BUGGY CODE ###

def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    L = [0 for i in range(n1+1)]
    R = [0 for i in range(n2+1)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = -1
    R[n2] = -1
    i = 0
    j = 0
    #global cnt
    cnt = 0

    for k in range(left, right):
        if (L[i] <= R[j] and L[i] != -1) or R[j] == -1:
            A[k] = L[i]
            i = i+1
            cnt +=1
        
        else:
            A[k] = R[j]
            j = j+1
            cnt +=1
    return cnt

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         cnt1 = mergeSort(A, left, mid)
         cnt2 = mergeSort(A, mid, right)
         cnt3 = merge(A, left, mid, right)
         return cnt1+cnt2+cnt3
    else:
        return 0

n = input()
A = list(map(int, input().split()))
cnt = mergeSort(A, 0, len(A))
print(*A)
print(str(cnt))

### FIXED CODE ###

def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    #L = [0 for i in range(n1+1)]
    #R = [0 for i in range(n2+1)]
    #for i in range(n1):
    #    L[i] = A[left+i]
    #for i in range(n2):
    #    R[i] = A[mid+i]
    L = A[left:mid]
    R = A[mid:right]
    L.append(float('inf'))
    R.append(float('inf'))
    i = 0
    j = 0
    global cnt

    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        
        else:
            A[k] = R[j]
            j = j+1
    return cnt

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         mergeSort(A, left, mid)
         mergeSort(A, mid, right)
         merge(A, left, mid, right)
    else:
        return 0

n = input()
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, len(A))
print(*A)
print(str(cnt))
### BUGGY CODE ###

l = [str(i) for i in input().split()]

a = int(l[0])
b = int(l[2])
op = l[1]

while True:

    if op == "+":
        print(a+b)
        
    elif op == "-":
        print(a-b)
        
    elif op == "*":
        print(a*b)
        
    elif op == "/":
        print(a//b)
     
    elif op == "?":
        break

### FIXED CODE ###

while True:

    l = [str(i) for i in input().split()]

    a = int(l[0])
    b = int(l[2])
    op = l[1]

    if op == "+":
        print(a+b)
        
    elif op == "-":
        print(a-b)
        
    elif op == "*":
        print(a*b)
        
    elif op == "/":
        print(a//b)
     
    elif op == "?":
        break
### BUGGY CODE ###

N, M = map(int, input().split())
H = [0]*N
H = list(map(int, input().split()))
Roads = [list(map(int, input().split())) for i in range(M)]
FP = [0]*N

for i in range(1,N+1):
  Opp = []
  t = 0
  if FP[i-1] == 0:
    for j in range(M):
      if i in Roads[j]:
        if i == Roads[j][0]:
          Opp.append(Roads[j][1])
        else:
          Opp.append(Roads[j][0])
    
    if len(Opp) == 0:
      FP[i-1] = 1
      continue
    
    for j in Opp:
      if H[j-1] < H[i-1]:
        FP[j-1] = -1
        t += (-FP[j-1])
    
    if t == len(Opp):
      FP[i-1] = 1

print(FP.count(1))

### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
near_max = [0]*N
for i in range(M):
  a, b = map(int, input().split())
  near_max[a-1] = max(near_max[a-1], H[b-1])
  near_max[b-1] = max(near_max[b-1], H[a-1])

ans = 0
for i in range(N):
  if near_max[i] < H[i]:
    ans += 1

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

"""

入れる場所とそこから波及する場所の最大距離が魔法使用回数

魔法使用回数を決め打ちしてdp？

魔法をp回使うとすると、左p箇所のうち最小の場所から入れるのが最適になる
heapを使うか～

2000 * 2000 * log(2000)
間に合うかなぁ～

4*10**7かぁ
"""

import heapq

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

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

ans = float("inf")

for p in range(N):

    now = x * p

    q = []

    for i in range(-1*p , 0):
        heapq.heappush(q,[a[i] , i])

    for i in range(N):

        heapq.heappush(q , [a[i] , i])

        while q[0][1] < i - p:
            heapq.heappop(q)

        now += q[0][0]

    ans = min(ans , now)

print (ans)


### FIXED CODE ###

"""

入れる場所とそこから波及する場所の最大距離が魔法使用回数

魔法使用回数を決め打ちしてdp？

魔法をp回使うとすると、左p箇所のうち最小の場所から入れるのが最適になる
heapを使うか～

2000 * 2000 * log(2000)
間に合うかなぁ～

4*10**7かぁ

各項からn個左を見た時のaの最小値を求めておく!!!
"""

lis = []

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

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

ans = [x * i for i in range(N)]

for i in range(N):

    nmin = float("inf")
    cnt = 0

    for j in range(i,i-N,-1):

        nmin = min(nmin,a[j])
        ans[cnt] += nmin

        cnt += 1

print (min(ans))

#heapq解(TLE)

"""
import heapq

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

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

ans = float("inf")

maxi = 0

for p in range(N):

    now = x * p

    q = []

    for i in range(-1*p , 0):
        heapq.heappush(q,[a[i] , i])

    for i in range(N):

        heapq.heappush(q , [a[i] , i])

        while q[0][1] < i - p:
            heapq.heappop(q)

        now += q[0][0]
        maxi = max(maxi , i - q[0][1]) 

    ans = min(ans , now)

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

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

fact = [1] * (n + 2)

for i in range(1, n + 2):
    fact[i] = i * fact[i - 1]

def nCm(n, m):
    global fact
    return fact[n] // (fact[m] * (fact[n - m]))

saw = [-1] * n
left = 0
right = 0
for i in range(n):
    if saw[a[i] - 1] == -1:
        saw[a[i] - 1] = i
    else:
        left, right = saw[a[i] - 1], n - i
        break

for i in range(1, n + 2):
    if i == 1:
        print(n)
    elif left + right >= i - 1:
        print((nCm(n + 1, i) - nCm(left + right, i - 1) % 1000000007))
    else:
        print(nCm(n + 1, i) % 1000000007)


### FIXED CODE ###

def power(x, n):
    y = 1
    while n > 0:
        if n % 2 == 0:
            x = (x * x) % (10 ** 9 + 7)
            n = n // 2
        else:
            y = (y * x) % (10 ** 9 + 7)
            n = n - 1
    return y


MOD = 10 ** 9 + 7

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

fact = [1] * (n + 2)
inv = [1] * (n + 3)

for i in range(1, n + 2):
    fact[i] = (i * fact[i - 1]) % MOD
    inv[i] = power(fact[i], MOD - 2) % MOD


def nCm(n, m):
    global fact
    global inv
    return fact[n] * inv[m] % MOD * inv[n - m] % MOD


saw = [-1] * n
left = 0
right = 0
for i in range(n):
    if saw[a[i] - 1] == -1:
        saw[a[i] - 1] = i
    else:
        left, right = saw[a[i] - 1], n - i
        break

for i in range(1, n + 2):
    if i == 1:
        print(n)
    elif left + right >= i - 1:
        print((nCm(n + 1, i) - nCm(left + right, i - 1)) % MOD)
    else:
        print(nCm(n + 1, i))
### BUGGY CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
var1 = [0] * (S + 1)
var1[0] = pow(2, N, 998244353)
var2 = pow(2, 998244353 - 2, 998244353)
m = 0
for all in A:
    m = all+m
    funcvar1=min(S, m)
    for val in reversed(range(all,funcvar1+1)):
        var1[val] = (var1[val] + var1[val - all] * var2) % 998244353
ans=var1[S]
print(ans)

### FIXED CODE ###

import numpy as np
def finalFunc(n,s,A):
    var=np.array([0 for i in range(min(3001,s+1))])
    var[0]=1
    for i in A:
        tmp=var[:-i].copy()
        var*=2
        var[i:]+=tmp
        var%=998244353
    return var[s]
n,s=map(int,input().split())
A=list(map(int,input().split()))
print(finalFunc(n,s,A))
### BUGGY CODE ###

from collections import Counter

N, P = map(int, input().split())
S = input()

sum = 0
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i]) % P == 0:
            sum += i+1
    print(sum)
    exit()

m = []
for i in range(N):
    m.append(int(S[i:]) % P)
    
mc = Counter(m)

for v in mc.values():
    if v > 1:
        sum += v*(v-1)/2

sum += mc[0]

print(int(sum))

### FIXED CODE ###

from collections import Counter

N, P = map(int, input().split())
S = input()

sum = 0
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i]) % P == 0:
            sum += i+1
    print(sum)
    exit()

m = []
t = 1
q = 0
for i in range(N,0,-1):
    q = ((int(S[i-1]) % P) * t + q) % P
    m.append(q)
    t = (10 * t) % P
    
mc = Counter(m)

for v in mc.values():
    if v > 1:
        sum += v*(v-1)//2

sum += mc[0]

print(sum)
### BUGGY CODE ###

# import bisect
from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

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

    for i in range(N):
        cnt = 0

        c=Counter(A[:i]+A[i+1:])
        values,counts=zip(*c.most_common())
        for j in counts:
            if j>=2:
                cnt+=j*(j-1)//2
        print(cnt)



resolve()

### FIXED CODE ###

from collections import Counter

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

    ans=0
    c = Counter(A)
    values, counts = zip(*c.most_common())
    for j in counts:
        if j >= 2:
            ans += j * (j - 1) // 2

    for i in A:
        if c[i]>=3:
            print(ans-(c[i]*(c[i]-1)//2-(c[i]-1)*(c[i]-2)//2))
        elif c[i]==2:
            print(ans-1)
        else:
            print(ans)






resolve()
### BUGGY CODE ###

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

s = [a[0]]
for i in range(1, n):
    s.append(s[i-1]+a[i])

cnt = 0
for i in range(n):
    for j in range(i, n):
        buf = s[j] - s[i-1] if (i >= 1) else s[j]
        if buf == 0:
            cnt += 1 
print(cnt) 

### FIXED CODE ###

'''
https://beta.atcoder.jp/contests/agc023/submissions/2426081
'''
n = int(input())
A = map(int, input().split())
B = {0:1}
s = 0
ans = 0
for a in A:
    s += a
    B_s = B.get(s, 0) 
    ans += B_s
    B[s] = B_s + 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split(" "))
A = list(map(int, input().split(" ")))
A = [0] + A
for i in range(1, N + 1):
    A[i] += A[i - 1]

for i in range(1, N + 1):
    A[i] -= i

rem_count = [0 for i in range(K)]
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
    if i - K >= 0:
        rem_count[A[i - K] % K] -= 1
    ans += rem_count[A[i] % K]
    rem_count[A[i] % K] += 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split(" "))
A = list(map(int, input().strip().split(" ")))
A = [0] + A
for i in range(1, N + 1):
    A[i] += A[i - 1]
    A[i - 1] -= i - 1
A[N] -= N

rem_count = {}
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
    if i - K >= 0:
        rem_count[A[i - K] % K] -= 1
    if A[i] % K in rem_count:
        ans += rem_count[A[i] % K]
        rem_count[A[i] % K] += 1
    else:
        rem_count[A[i] % K] = 1

print(ans)