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

import heapq

N,M=map(int,input().split())
A=list(map(int,input().split()))
heapq.heapify(A)
for _ in range(M):
  b,c=map(int,input().split())
  for _ in range(b):
    a=heapq.heappop(A)
    if c>a:
      heapq.heappush(A,c)
    else:
      heapq.heappush(A,a)
      break
print(sum(A))


### FIXED CODE ###

N,M=map(int,input().split())
A=map(int,input().split())
L=[(1,a) for a in A]
for _ in range(M):
  b,c=map(int,input().split())
  L.append((b,c))
L=sorted(L,key=lambda x: x[1],reverse=True)
ans,k=0,0
for n,a in L:
  if n+k>=N:
    ans+=a*(N-k)
    break
  else:
    ans+=a*n
    k+=n
print(ans)
### BUGGY CODE ###

import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    h, w = map(int, read().split())
    s = [list(read()) for _ in range(h)]
    row = [[0 for _ in range(w)] for _ in range(h)]
    col = [[0 for _ in range(w)] for _ in range(h)]
    for i in range(h):
        c = 0
        for j in range(w):
            if s[i][j] == "#":
                for k in range(j - c, j):
                    row[i][k] = c
                c = 0
            else:
                c += 1
        for k in range(w - c, w):
            row[i][k] = c
    for i in range(w):
        c = 0
        for j in range(h):
            if s[j][i] == "#":
                for k in range(j - c, j):
                    col[k][i] = c
                c = 0
            else:
                c += 1
        for k in range(h - c, h):
            col[k][i] = c
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(row[i][j] + col[i][j], ans)
    print(ans - 1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    h, w = map(int, read().split())
    s = [list(read()) for _ in range(h)]
    row = [[0 for _ in range(w)] for _ in range(h)]
    col = [[0 for _ in range(w)] for _ in range(h)]
    for i in range(h):
        c = 0
        for j in range(w):
            if s[i][j] == "#":
                for k in range(j - c, j):
                    row[i][k] = c
                c = 0
            else:
                c += 1
        for k in range(w - c, w):
            row[i][k] = c
    for i in range(w):
        c = 0
        for j in range(h):
            if s[j][i] == "#":
                for k in range(j - c, j):
                    col[k][i] = c
                c = 0
            else:
                c += 1
        for k in range(h - c, h):
            col[k][i] = c
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(row[i][j] + col[i][j], ans)
    print(ans - 1)

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

m1 = 1046527
_dict = [""] * m1


def insert(k):
    i = 0

    while True:
        ix = _h(k, i)
        if _dict[ix] == "":
            _dict[ix] = k
            return
        else:
            i += 1


def find(k):
    i = 0

    while True:
        ix = _h(k, i)
        if _dict[ix] == k:
            return True
        elif _dict[ix] == "":
            return False
        else:
            i += 1

    return False


def _h(k, i):
    return ((k % m1) + i * (1 + k % (m1 - 1))) % m1


def to_int(s):
    ret = 0
    i = 1
    for j in range(len(s)):
        e = s[len(s) - j - 1]

        if e == 'A':
            ret += 1 * i
        elif e == 'C':
            ret += 2 * i
        elif e == 'G':
            ret += 3 * i
        elif e == 'T':
            ret += 4 * i
        i *= 5

    return ret


if __name__ == '__main__':
    n = int(input())

    for _ in range(n):
        cmd, val = input().split()

        if cmd[0] == "i":
            insert(to_int(val))
        else:
            ans = "yes" if find(to_int(val)) else "no"
            print(ans)

### FIXED CODE ###

M = 1046527
L = 14
H = [""] * M
 
def getChar(ch):
    if ch == 'A':
        return 1
    elif ch == 'C':
        return 2
    elif ch == 'G':
        return 3
    elif ch == 'T':
        return 4
    else:
        return 0
 
def getKey(strings):
    Sum = 0
    p = 1
    for i in xrange(len(strings)):
        Sum += p * getChar(strings[i])
        p *= 5
 
    return Sum
 
def h1(key):
    return key % M
 
def h2(key):
    return 1 + (key % (M-1))
 
def find(strings):
    key = getKey(strings)
    i = 0
    while True:
        h = (h1(key) + i * h2(key)) % M
        if H[h] == strings:
            return 1
        elif len(H[h]) == 0:
            return 0
        else:
            i += 1
    return 0
 
def insert(strings):
    key = getKey(strings)
    i = 0
    while True:
        h = (h1(key) + i * h2(key)) % M
        if H[h] == strings:
            return 1
        elif len(H[h]) == 0:
            H[h] = strings
            return 0
        else:
            i += 1
    return 0
 
def main():
    n = input()
    for i in xrange(n):
        com = raw_input().split()
        if com[0][0] == 'i':
            insert(com[1])
        else:
            if find(com[1]):
                print 'yes'
            else:
                print 'no'
    return 0
 
main()
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
Cs = list(mapint())
LR = []
for i in range(Q):
    l, r = mapint()
    LR.append((l, r, i))
LR.sort(key=lambda x:x[1])
A = [0]*N

def add(A,a,w):#リストに値を追加する関数
    x = a
    while x <= N:
        A[x-1] += w
        x += x&(-x)

def sums(A,a):#k番目までの和
    x = a
    S = 0
    while x != 0:
        S += A[x-1]
        x -= x&(-x)
    return S

ans = [0]*Q
idx = 0
last_appeared = [-1]*(N+1)
for i in range(N):
    c = Cs[i]
    if last_appeared[c]==-1:
        last_appeared[c] = i+1
        add(A, i+1, 1)
    else:
        past = last_appeared[c]
        last_appeared[c] = i+1
        add(A, past, -1)
        add(A, i+1, 1)
    while idx<Q and LR[idx][1]<=i+1:
        l, r, ans_idx = LR[idx]
        ans[ans_idx] = sums(A, r)-sums(A, l-1)
        idx += 1
for a in ans:
    print(a)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
Cs = list(mapint())
LR = []
for i in range(Q):
    l, r = mapint()
    LR.append((l, r, i))
LR.sort(key=lambda x:x[1])
A = [0]*N

def add(A,a,w):#リストに値を追加する関数
    x = a
    while x <= N:
        A[x-1] += w
        x += x&(-x)

def sums(A,a):#k番目までの和
    x = a
    S = 0
    while x != 0:
        S += A[x-1]
        x -= x&(-x)
    return S

ans = [0]*Q
idx = 0
dic = {}
for i in range(N):
    c = Cs[i]
    if c not in dic:
        dic[c] = i+1
        add(A, i+1, 1)
    else:
        past = dic[c]
        dic[c] = i+1
        add(A, past, -1)
        add(A, i+1, 1)
    while idx<Q and LR[idx][1]<=i+1:
        l, r, ans_idx = LR[idx]
        ans[ans_idx] = sums(A, r)-sums(A, l-1)
        idx += 1
for a in ans:
    print(a)
### BUGGY CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    ans = 1
    for i in range(int(p ** (1 / n)) + 1, 1, -1):
        if p % (i ** n) == 0:
            ans = i
            print(ans)
            break
    if ans == 1:
        print(ans)




### FIXED CODE ###

import collections

def prime_return(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n, p = map(int, input().split())
t = collections.Counter(prime_return(p))
ans = 1
for k, v in t.items():
    if v >= n:
        ans *= (k ** (v // n))
print(ans)
### BUGGY CODE ###

from fractions import gcd

def gcds(List):
    __ = 0
    for _ in List:
        __ = gcd(__, _)
    return __

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

x = 0
y = gcds(l)

for i in range(y):
    if y % 2 ==0:
        x += 1
        y /= 2

print(x)

### FIXED CODE ###

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

z = 0
y = []

for i in range(n):
    x = l[i]
    for j in range(max(l)):
        if x % 2 ==0:
            z += 1
            x = int(x/2)
        else:
            y.append(z)
            z = 0
            break

#print(y)
print(min(y))
### BUGGY CODE ###

h,w,m=map(int, input().split())
hw=[list(map(int, input().split())) for _ in range(m)]

tate=[]
yoko=[]

for i in range(m):
    tate.append(hw[i][0])
    yoko.append(hw[i][1])

from collections import Counter
tatec=Counter(tate).most_common()
yokoc=Counter(yoko).most_common()

c_1_max=tatec[0][1]
c_1s=[]
for t in tatec:
    if t[1]==c_1_max:
        c_1s.append(t[0])
    else:
        break

c_2_max=yokoc[0][1]
c_2s=[]
for y in yokoc:
    if y[1]==c_2_max:
        c_2s.append(y[0])
    else:
        break

flag=False

for c_1 in c_1s:
    for c_2 in c_2s:
        tmp_flag=0
        for i in range(m):
            h_i=hw[i][0]
            w_i=hw[i][1]
            if h_i!=c_1 or w_i!=c_2:
                tmp_flag+=1
        if tmp_flag==m:
            flag=True
        if flag:
            break
    if flag:
        break

print(max(tatec[0][1]+yokoc[0][1], 1) if flag else max(tatec[0][1]+yokoc[0][1]-1, 1))


### FIXED CODE ###

h,w,m=map(int, input().split())
hw=[list(map(int, input().split())) for _ in range(m)]

y_list=[0]*h
x_list=[0]*w

for h_i, w_i in hw:
    y_list[h_i-1]+=1
    x_list[w_i-1]+=1

my_cnt=max(y_list)
mx_cnt=max(x_list)

y_cnt=0
x_cnt=0

my_set=set()
mx_set=set()

for h_i, w_i in hw:
    if y_list[h_i-1]==my_cnt:
        my_set.add(h_i-1)
    if x_list[w_i-1]==mx_cnt:
        mx_set.add(w_i-1)

cnt=0
for h_i, w_i in hw:
    if y_list[h_i-1]==my_cnt and x_list[w_i-1]==mx_cnt:
        cnt+=1

print(my_cnt+mx_cnt-1 if cnt==len(my_set)*len(mx_set) else my_cnt+mx_cnt)
### BUGGY CODE ###

N = int(input())

table = [0] * (N+1)

for i in range(1,N+1):
    for j in range(1,N+1):
        if j % i == 0:
            table[j] += 1

ans = 0
for i in range(1,N+1):
    ans += i * table[i]

print(ans)

### FIXED CODE ###

N = int(input())

table = [0] * (N+1)

for i in range(1,N+1):
    for j in range(i,N+1,i):
        table[j] += 1

ans = 0
for i in range(1,N+1):
    ans += i * table[i]

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

N,M = list(map(int,input().split()))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

a2 = [int(i//2) for i in map(int,input().split())]
count2 = set()
for i in a2:
    prime = prime_factorize(i)
    count2.add(prime.count(2))
if len(count2) == 1:

    if len(a2) == 1:
        div = M//a2[0]
        print((div+1)//2)
    else:
        gcda = a2[0]*a2[1]//gcd(a2[0],a2[1])
        for i in range(2,N):
            gcda = gcda*a2[i]//gcd(gcda,a2[i])
        div = M//gcda
        print((div+1)//2)
    
else:
    print(0)

### FIXED CODE ###

N,M = list(map(int,input().split()))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def twocount(n):
    c = 0
    while n%2 == 0:
        n //= 2
        c += 1
    return c
 
a2 = [int(i//2) for i in map(int,input().split())]
count2 = set()
for i in a2:
    tc = twocount(i)
    count2.add(tc)
if len(count2) == 1:
 
    if len(a2) == 1:
        div = M//a2[0]
        print((div+1)//2)
    else:
        gcda = a2[0]*a2[1]//gcd(a2[0],a2[1])
        for i in range(2,N):
            gcda = gcda*a2[i]//gcd(gcda,a2[i])
        div = M//gcda
        print((div+1)//2)
    
else:
    print(0)
### BUGGY CODE ###

N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
  a,b=map(int,input().split())
  w.append(a)
  v.append(b)
dp=[[0]*(W+1) for i in range(N+1)]
for i in range(N):
  for j in range(W+1):
      if j-w[i]>=0:
          dp[i+1][j]=dp[i][j-w[i]]+v[i]
      dp[i+1][j]=max(dp[i+1][j],dp[i][j])
print(dp[N][W])

### FIXED CODE ###

# D - Knapsack 1 Educational DP Contest / DP
import numpy as np

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

dp = np.zeros(W+1, dtype=np.int64)
for _ in range(N):
    w,v = map(int,input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])

ans = dp.max()
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
f=l[0]
from fractions import gcd

for i in l:
    f=f*i//gcd(f,i)
mod=10**9+7
print(sum((f//a)%mod for a in l )%mod)

### FIXED CODE ###

def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    b,u,v=mod,1,0
    while b:
      t=iu//b;iu,b=b,iu%b;u-=t*v;u,v=v,u
    ans+=(f*u%mod)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()
### BUGGY CODE ###

#C問題  
N,Q=map(int,input().split())
S=str(input())
Slist=list(S)
LR=[list(map(int,input().split())) for i in range(Q)]
pile=[0 for i in range(N)]
for i in range(N-1):
    if Slist[i] == "A" and Slist[i+1] == "C":
        pile[i]=1
pile_sum=[0 for i in range(N)]
for i in range(N):
    pile_sum[i]=sum(pile[:i])
for i in range(Q):
    right=pile_sum[LR[i][1]-1]
    left=pile_sum[LR[i][0]-1]
    print(right-left)

### FIXED CODE ###

#C問題  
N,Q=map(int,input().split())
S=str(input())
Slist=list(S)
pile=[0 for i in range(N)]
for i in range(N-1):
    if i == 0:
        pass
    else:
        pile[i]=pile[i-1]
  
    if Slist[i] == "A" and Slist[i+1] == "C":
        pile[i]+=1
pile[-1]=pile[-2]
pile.insert(0,0)
for i in range(Q):
    l,r=map(int,input().split())
    print(pile[r-1]-pile[l-1])
### BUGGY CODE ###

# wa
import copy
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [1] * n
for _ in range(k):
    for i in range(n):
        light = 0
        for j in range(n):
            if i < j:
                if (j - a[j] - 0.5) < i:
                    light += 1
            else:
                if (j + a[j] + 0.5) > i:
                    light += 1
        b[i] = light
    a = copy.deepcopy(b)
for i in a:
    print(i, end=' ')

### FIXED CODE ###

# ac
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8[::1],)', cache=True)
def update(a):
    n = len(a)
    b = np.zeros_like(a)       # aと同じ形状の配列を生成(https://deepage.net/features/numpy-zeros.html)
    for i, x in enumerate(a):  # enumerateはindex, valueを返す
        l = max(0, i - x)      # lampの照らす範囲の下限（左側）
        r = min(n - 1, i + x)  # lampの上限（右側）
        b[l] += 1              # 以下imos法
        if r + 1 < n:          # r+1はx=nの時（最後のサイクル）r+1=nでindexの指定に失敗するから弾く（indexは0~n-1）
            b[r + 1] -= 1
    b = np.cumsum(b)           # bの要素の累積和（フィボナッチ数列みたいな）（imos法の締め）
    return b


n, k = map(int, readline().split())
a = np.array(read().split(), np.int64)

k = min(k, 41)                 # 今回の制限範囲のnなら41回も試行すればaの値が全て上限に達するのでそれ以上の試行は不要（解説PDF）
for _ in range(k):
    a = update(a)
print(' '.join(map(str, a)))   # joinメソッドはstrを''で区切って連結する
### BUGGY CODE ###

N = int(input())
sum = 0
for i in range(1, N):
    sum += i
print(sum)

### FIXED CODE ###

N = int(input())
print((1 + (N - 1)) * (N - 1) // 2)
### BUGGY CODE ###

s=input()
x,y = [int(i) for i in input().split()]

#print(s)

susumu = [0]
for i in range(len(s)):
    if s[i] == 'F':
        susumu[-1] += 1
    else:
        susumu.append(0)

#print(susumu)

syokiti = susumu.pop(0)

susumu_NS = [i for i in susumu[::2] if i != 0]
susumu_EW = [i for i in susumu[1::2] if i != 0]

x -= syokiti

# ＥＷの部分和でx? NSの部分和でy？

LL = sum(susumu_NS)+2
dp = [[0 for i in range(4*LL+2*len(s))] for j in range(1+len(susumu_NS))]
dp[0][2*LL+len(s)] = 1


for j in range(len(susumu_NS)):
#    print('j='),
#    print(j)
    for i in range(LL+len(s),3*LL+len(s)):
#        a=0
#        print(i+susumu_NS[j])
        dp[j+1][i] = dp[j][i+susumu_NS[j]] | dp[j][i-susumu_NS[j]]

can_y = 0
if dp[len(susumu_NS)][y+2*LL+len(s)] != 0:
    can_y = 1
#print(susumu_NS)
#print(can_y)
    
#########################################
LL = sum(susumu_EW)+2
dp = [[0 for i in range(4*LL+len(s))] for j in range(1+len(susumu_EW))]
dp[0][2*LL+len(s)] = 1

for j in range(len(susumu_EW)):
#    print('j='),
#    print(j)
    for i in range(LL+len(s),3*LL+len(s)):
#        a=0
#        print(i+susumu_NS[j])
        dp[j+1][i] = dp[j][i+susumu_EW[j]] | dp[j][i-susumu_EW[j]]

can_x = 0
if dp[len(susumu_EW)][x+2*LL+len(s)] != 0:
    can_x = 1

#print(can_x)

if can_x == 1 & can_y == 1:
    print('Yes')
else:
    print('No')








### FIXED CODE ###

import numpy as np

s=input()
x,y = [int(i) for i in input().split()]

#print(s)

susumu = [0]
for moji in s:
    if moji == 'F':
        susumu[-1] += 1
    else:
        susumu.append(0)

#print(susumu)

syokiti = susumu[0]

susumu_NS = [i for i in susumu[1::2] if i!=0]
susumu_EW = [i for i in susumu[2::2] if i!=0]

x -= syokiti

#print(susumu)
#print(susumu_NS)
#print(susumu_EW)
# ＥＷの部分和でx? NSの部分和でy？

LL = len(s)+2
dp = np.zeros(LL*2, dtype=bool)
dp[LL] = 1
for j in range(len(susumu_NS)):
    dpleft =np.r_[dp[susumu_NS[j]:],np.zeros(susumu_NS[j], dtype=bool)]
    dpright=np.r_[np.zeros(susumu_NS[j], dtype=bool),dp[:-susumu_NS[j]]]
    dp = dpleft|dpright
#    print(dp)

can_y = 0
if dp[y+LL] != False:
    can_y = 1
#print(dp)
#print(susumu_NS)

#########################################
LL = len(s)+2
dp = np.zeros(LL*2, dtype=bool)
dp[LL] = 1
for j in range(len(susumu_EW)):
    dpleft =np.r_[dp[susumu_EW[j]:],np.zeros(susumu_EW[j], dtype=bool)]
    dpright=np.r_[np.zeros(susumu_EW[j], dtype=bool),dp[:-susumu_EW[j]]]
    dp = dpleft|dpright
#    print(dp)

can_x = 0
if dp[x+LL] != False:
    can_x = 1

#print(dp)
#print(susumu_EW)

if can_x == 1 & can_y == 1:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n = int(input())

L = [0] * (n + 1)
for x in range(1, n + 1):
    for y in range(1, n - x):
        for z in range(1, n - x - y):
            tmp = x * x + y * y + z * z + x * y + y * z + z * x
            if tmp > n:
                continue
            L[tmp] += 1

for l in L[1:]:
    print(l)

### FIXED CODE ###

import math

n = int(input())
max = int(math.sqrt(n) + 1)
L = [0] * (n + 1)
for x in range(1, max):
    for y in range(1, max):
        for z in range(1, max):
            tmp = x * x + y * y + z * z + x * y + y * z + z * x
            if tmp > n:
                continue
            L[tmp] += 1

for i in range(1, n + 1):
    print(L[i])
### BUGGY CODE ###

import heapq
N,K=map(int,raw_input().split())
c=[]
for i in range(N):
	a,b=map(int,raw_input().split())
	for j in range(b):
		heapq.heappush(c,a)

for i in range(len(c)):
	val=heapq.heappop(c)
	if i==K-1:
		print val
		break


### FIXED CODE ###

import heapq
N,K=map(int,raw_input().split())
c=[]
for i in range(N):
	heapq.heappush(c, tuple( map(int,raw_input().split()) ) )

cnt=0
for i in range(len(c)):
	val=heapq.heappop(c)
	cnt+=val[1]
	if K<=cnt:
		print val[0]
		break
### BUGGY CODE ###

N, Ma, Mb = map(int,input().split())
C = [map(int,input().split()) for i in range(N)]
INF = 40000
dp = [[[INF]*401 for i in range(401)] for i in range(N+1)]
dp[0][0][0] = 0
for i in range(1,N+1):
  a,b,c = C[i-1]
  for j in range(401):
      for k in range(401):
        dp[i][j][k] = dp[i-1][j][k]
        if j >= a and k >= b and dp[i-1][j-a][k-b] != INF:
            dp[i][j][k] = min(dp[i][j][k],dp[i-1][j-a][k-b]+c)
ans = INF
Ma2,Mb2 = Ma,Mb
while max(Ma2,Mb2) < 401:
  ans = min(ans,dp[-1][Ma2][Mb2])
  Ma2 += Ma
  Mb2 += Mb    

print(ans if ans != INF else -1)


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
table = []
for i in range(N):
  a,b,c = map(int, input().split())
  table.append([a,b,c])
inf = 10**9
dp = [[[inf]*401 for i in range(401)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(1,N+1):
  a,b,c = table[i-1]
  for j in range(401):
    for k in range(401):
      dp[i][j][k] = dp[i-1][j][k]
      if 400>=j-a>=0 and 400>=k-b>=0:
        dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
ans = 10**9
i = 1
while max(Ma,Mb)*i <= 400:
  ans = min(ans,dp[N][Ma*i][Mb*i])
  i += 1
if ans == 10**9:
  ans = -1
print(ans)
### BUGGY CODE ###

def main():
  n, p = map(int, input().split()) 
  s = input() 

  ans = 0

  if p == 2:
    for i, si in enumerate(s):
      if int(si) % 2 == 0:
        ans += (i+1)
    print(ans)
    exit()

  if p == 5:
    for i, si in enumerate(s):
      if int(si) % 5 == 0:
        ans += (i+1)
    print(ans)
    exit()

  rem_dict = {i: 0 for i in range(p)}

  for i in range(n):
    rem = int(s[i:]) % p
    rem_dict[rem] += 1

  ans += rem_dict[0]
  for rem, num in rem_dict.items():
    ans += (num * (num  - 1)) // 2

  print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  n, p = map(int, input().split()) 
  s = input() 

  ans = 0

  if p == 2:
    for i, si in enumerate(s):
      if int(si) % 2 == 0:
        ans += (i+1)
    print(ans)
    exit()

  if p == 5:
    for i, si in enumerate(s):
      if int(si) % 5 == 0:
        ans += (i+1)
    print(ans)
    exit()

  rem_list = [0] * p
  cof = 1
  prev_rem = 0
  
  for i in range(n):
    rem = (int(s[n-1-i]) * cof + prev_rem) %  p
    ans += rem_list[rem]
    if rem == 0:
      ans += 1      
    rem_list[rem] += 1

    prev_rem = rem
    cof *= 10
    cof %= p

  print(ans)

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

H,W,D = map(int,input().split())
A = []
for i in range(H):
    A.append(list(map(int, input().split())))
Q = int(input())
L = []
R = []
for i in range(Q):
    l,r = map(int, input().split())
    L.append(l)
    R.append(r)
    
import numpy as np
A = np.array(A)
for i in range(Q):
    MP = 0
    point = L[i]
    for j in range(int((R[i] - L[i]) / D)):
        start = np.array(np.where(A == point)).T.reshape(2)
        end = np.array(np.where(A == (point+D))).T.reshape(2)
        MP += sum(abs(start - end))
        point += D
    print(MP)

### FIXED CODE ###

import numpy as np
H,W,D = map(int,input().split())
SUM = H*W
px = np.zeros(SUM+1)
py = np.zeros(SUM+1)
for i in range(1,H+1):
    A = list(map(int, input().split()))
    for j in range(len(A)):
        px[A[j]] = i
        py[A[j]] = j + 1

d = np.zeros(SUM+1)
for t in range(D+1,SUM+1):
    d[t] = d[t-D] + abs(px[t] - px[t-D])+ abs (py[t] - py[t-D]);
        
Q = int(input())
L = []
R = []
for i in range(Q): 
    l,r = map(int, input().split())
    print(int(d[r]-d[l]))
### BUGGY CODE ###

s=input()
q=int(input())
for i in range(q):
    que=list(map(str,input().split()))
    if int(que[0])==1:
        s=s[::-1]
    else:
        if int(que[1])==1:
            s=str(que[2])+s
        else:
            s=s+str(que[2])

print(s)

### FIXED CODE ###

from collections import deque
s=input()
q=int(input())
sd=deque()
for i in range(len(s)):
    sd.append(s[i])
count=0
for i in range(q):
    que=list(map(str,input().split()))
    if int(que[0])==1:
        count+=1
    else:
        if int(que[1])==1:
            if count%2==0:
                sd.appendleft(str(que[2]))
            else:
                sd.append(str(que[2]))
        else:
            if count%2==0:
                sd.append(str(que[2]))
            else:
                sd.appendleft(str(que[2]))
if count%2!=0:
    sd.reverse()

ans=''.join(sd)
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split(" "))
arr = list(map(int,input().split(" ")))

l=list()
l.append(0)

for i in range(1,n):
	mini= abs(arr[i] - arr[i-1]) + l[i-1]

	for j in range(2,min(k+1,i+1)):
		mini = min(mini, abs(arr[i] - arr[i-j]) + l[i-j])
	l.append(mini)

# print(l)
print(l[-1])

### FIXED CODE ###

n,k = map(int,input().split(" "))
arr = list(map(int,input().split(" ")))

l=list()
l.append(0)

for i in range(1,n):
	mini= abs(arr[i] - arr[i-1]) + l[i-1]

	for j in range(2,min(k+1,i+1)):
		mini = min(mini, abs(arr[i] - arr[i-j]) + l[i-j])
	l.append(mini)

# print(l)
print(l[-1])