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

N,H=map(int,input().split())
a=[];b=[]
for _ in range(N):
    ai,bi=map(int,input().split())
    a.append(ai)
    b.append(bi)
bb=[]
for i in range(N):
    if b[i]>=max(a):
        bb.append(b[i])
if sum(bb)>=H:
    print(len(bb))
else:
    ans=int((H-sum(bb))/max(a))+len(bb)
    if (H-sum(bb))%max(a)==0:
        print(ans)
    else:
        print(ans+1)

### FIXED CODE ###

N,H=map(int,input().split())
S=[[int(x) for x in input().split()] for _ in range(N)]
A,B=zip(*S)
A=max(A)
B=[b for b in B if b>A]
B.sort(reverse=True)
ans=0
cnt=0
for b in B:
    if H<=0:
        break
    cnt+=1
    H-=b
if H>0:
    cnt+=(H-1)//A+1
print(cnt)
### BUGGY CODE ###

n,m,k = map(int,input().split())
A = [int(p) for p in input().split()]
B = [int(p) for p in input().split()]
a,b = [0],[0]

a_apnd = a.append
b_apnd = b.append
for i in range(n):
  a_apnd(a[i]+A[i])
for i in range(m):
  b_apnd(b[i]+B[i])

count = 0
for i in range(n+1):
  res = k-a[i]
  if res<0:
    break
  for t in reversed(range(m+1)):
    if b[t] <= res:
      break
  if count<(i+t):
    count = i+t

print(count)

### FIXED CODE ###

n,m,k = map(int,input().split())
A = [int(p) for p in input().split()]
B = [int(p) for p in input().split()]
a,b = [0],[0]

a_apnd = a.append
b_apnd = b.append
for i in range(n):
  a_apnd(a[i]+A[i])
for i in range(m):
  b_apnd(b[i]+B[i])

count = 0
t = m
for i in range(n+1):
  if k<a[i]:
    break
  while b[t] > k-a[i]:
    t -= 1
  count = max(count,i+t)

print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000) 

N, Q = map(int, input().split())
T = [[] for i in range(2 * (10 ** 5))]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)

d = [0] * N

for i in range(Q):
    p, x = map(int, input().split())
    d[p - 1] += x

def dfs(u, v = -1):
    global d
    for p in T[u]:
        if p != v:
            d[p] += d[u]
            dfs(p, u)

dfs(0)


print(' '.join(map(str, d)))


### FIXED CODE ###

from sys import stdin,setrecursionlimit
input = stdin.readline
setrecursionlimit(1000000) 

N, Q = map(int, input().split())
T = [[] for _ in range(2 * (10 ** 5))]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)

d = [0] * N

for _ in range(Q):
    p, x = map(int, input().split())
    d[p - 1] += x

def dfs(u, v):
    global d
    for p in T[u]:
        if p == v:
            continue
        d[p] += d[u]
        dfs(p, u)

dfs(0, -1)

for v in d:
    print(v)
### BUGGY CODE ###

import math
def pri(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
ans = 0
a,b = map(int,input().split())
for i in range(1,int(min(a,b)**0.5)+1):
    if i in pri(a) and i in pri(b):
        ans += 1
print(ans+1)

### FIXED CODE ###

import math
def main():
    def pri(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
    ans = 0
    a,b = map(int,input().split())
    c = pri(a)
    d = pri(b)
    p = []
    if len(c) > 0:
        p.append(c[0])
    for i in range(len(c)-1):
        if c[i] != c[i+1]:
            p.append(c[i+1])
    for i in range(len(p)):
        if p[i] in d:
            ans += 1
    print(ans+1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
s = 1
x = 10 ** 9 + 7
for i in range(1, n+1):
    s = s * i % x
print(s)
### BUGGY CODE ###

s = input()
q = int(input())

rv = False
for i in range(q):
    line = input()
    if line[0] == '1':
        rv = ~rv
    else:
        ti, fi, ci = line.split()
        if (fi == '1' and rv) or (fi == '2' and not rv):
            s = s + ci
        else:
            s = ci + s
if rv:
    for i in range(1, len(s)+1):
        print(s[-i], end='')
    print('')
else:
    print(s)

### FIXED CODE ###

import sys
s = sys.stdin.readline()
s = s[:-1]
q = int(input())

front = ''
back = ''
rv = False
for i in range(q):
    line = input()
    if line[0] == '1':
        rv = not rv
    else:
        ti, fi, ci = line.split()
        if (fi == '1' and rv) or (fi == '2' and not rv):
            back += ci
        else:
            front += ci

if rv:
    s = back[::-1] + s[::-1] + front
else:
    s = front[::-1] + s + back
print(s)
### BUGGY CODE ###

N = int(input())
list_A = []
for i in range(N):
    a = int(input())
    if a in list_A:
        list_A.remove(a)
    else:
        list_A.append(a)
print(len(list_A))

### FIXED CODE ###

import collections
N = int(input())
list_A = [0]*N
for i in range(N):
    list_A[i] = int(input())
c = collections.Counter(list_A)
c_odd_even = [i%2 for i in list(c.values())]
print(sum(c_odd_even))
### BUGGY CODE ###

import math
A, B, C, D = map(int, input().split())

# CでもDでも割り切れない = 全体(a) - Cで割り切れる(b) + Dで割り切れる(c) + CでもDでも割り切れる(d)
lcm = C*D // math.gcd(C, D)

a, b, c, d = B-A+1, 0, 0, 0
for i in range(A, B+1):
  if i % C == 0: b += 1
  if i % D == 0: c += 1
  if i % lcm == 0: d += 1

print(a-b-c+d)

### FIXED CODE ###

import math
A, B, C, D = map(int, input().split())
 
# CでもDでも割り切れない = 全体(a) - Cで割り切れる(b) + Dで割り切れる(c) + CでもDでも割り切れる(d)
lcm = C*D // math.gcd(C, D)
a = B - A + 1
b = B // C - (A-1) // C
c = B // D - (A-1) // D
d = B // lcm - (A-1) // lcm

print(a-b-c+d)
### BUGGY CODE ###

import numpy
N=int(input())
A=list(map(int,input().split()))
Ap=numpy.cumsum(A)
A2=[abs(sum(A)-n*2) for n in Ap]
ans=0
x=A2.index(min(A2))+1
pl=max(sum(A[:x]),sum(A[x:]))
mi=min(sum(A[:x]),sum(A[x:]))
while mi<pl:
  mi+=1
  ans+=1
  if mi==pl:
    break
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
p=q=sum(A)
for i in range(N):
  p-=2*A[i]
  q=min(abs(p),q)
print(q)
### BUGGY CODE ###

import bisect
N = int(input())
Ln = list(map(int,input().split(' ')))

def binary_area_search(target_list: list, target_item: int) -> int:
    '''
    @params
    target_list: [1,3,5](ACC)
    target_item: 2

    @return
    return index
    '''
    low = 0
    high = len(target_list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = target_list[mid]
        if guess > target_item:
            if mid == 0:
                return 0
            if target_item > target_list[mid-1]:
                return mid 
            high = mid -1
        else:
            if mid == len(target_list) - 1:
                return None
            if target_list[mid+1] > target_item:
                return mid + 1 
            low = mid + 1
    return None

def main():
    '''
    N^2*logN
    '''
    Ln.sort()
    count = 0
    for a in range(N):
        a_l = Ln[N-a-1]
        for b in range(a+1, N):
            b_idx = N-b-1
            b_l = Ln[b_idx]
            c_threshold = a_l - b_l
            #c_list = Ln[0:N-b-1]
            c_idx = bisect.bisect_right(Ln,c_threshold)
            #c_idx = binary_area_search(c_list,c_threshold)
            if c_idx >= b_idx:
                continue
            count += b_idx - c_idx
    print(count)

def main2():
    '''
    N^2
    '''
    Ln.sort(reverse=True)
    count = 0
    for a in range(N):
        a_l = Ln[a]
        current_min = N-1
        b = a +1
        while b <= current_min:
            c_idx = current_min
            bc = Ln[b] + Ln[c_idx]
            if a_l < bc:
                count += (current_min - b)
                b += 1
                continue
            current_min -= 1
    print(count)

def main3():
    '''
    N^2*logN
    '''
    Ln.sort()
    count = 0
    for a in range(N):
        a_l = Ln[N-a-1]
        for b in range(a+1, N):
            b_idx = N-b-1
            b_l = Ln[b_idx]
            c_threshold = a_l - b_l
            c_list = Ln[0:b_idx+1]
            c_idx = bisect.bisect_right(c_list,c_threshold)
            #c_idx = binary_area_search(c_list,c_threshold)
            if c_idx >= b_idx:
                continue
            count += b_idx - c_idx
    print(count)

main3()

### FIXED CODE ###

N = int(input())
Ln = list(map(int,input().split(' ')))
Ln.sort(reverse=True)

count = 0
for a in range(N):
    a_l = Ln[a]
    current_min = N-1
    b = a +1
    while b <= current_min:
        c_idx = current_min
        bc = Ln[b] + Ln[c_idx]
        if a_l < bc:
            count += (current_min - b)
            b += 1
            continue
        current_min -= 1
    '''
    for b in range(a+1, N):
        if b >= current_min:
            break
        for c in range(b+1,N):
            c_idx = current_min
            bc = Ln[b] + Ln[c_idx]
            if a_l < bc:
                count += (current_min - b)
                break
            current_min -= 1
    '''
print(count)
### BUGGY CODE ###

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

ans = []

if N%2 == 0:
    for i in range(N):
        if i%2 == 0:
            ans.append(a[i])
        else:
            ans.insert(0,a[i])
else:
    for i in range(N):
        if i%2 == 0:
            ans.insert(0,a[i])
        else:
            ans.append(a[i])

for i in range(N):
    print(ans[i],end=" ")

### FIXED CODE ###

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

from collections import deque

ans = deque()

if N%2 == 0:
    for i in range(N):
        if i%2 == 0:
            ans.append(a[i])
        else:
            ans.appendleft(a[i])
else:
    for i in range(N):
        if i%2 == 0:
            ans.appendleft(a[i])
        else:
            ans.append(a[i])

for i in range(N):
    print(ans[i],end=" ")
### BUGGY CODE ###

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

dots = []
for _ in range(N):
    x, y = map(int, input().split())
    dots.append((x, y))
    

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)


### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    pad1=[-2,-2]
    pad2=[[-2]*(W+4)]*2
    s=pad2+[pad1+x+pad1 for x in s]+pad2
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch+2,cw+2)]
    q2=[]
    s[ch+2][cw+2]=0
    def mark(c,h,w):
        #if 0<=h<H and 0<=w<W and s[h][w]==-1:
        if s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        #print(q1)
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh+2][dw+2]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()


### FIXED CODE ###

def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    pad1=[-2,-2]
    pad2=[[-2]*(W+4)]*2
    s=pad2+[pad1+x+pad1 for x in s]+pad2
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch+2,cw+2)]
    q2=[]
    s[ch+2][cw+2]=0
    def mark(c,h,w):
        #if 0<=h<H and 0<=w<W and s[h][w]==-1:
        if s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        #print(q1)
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh+2][dw+2]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from itertools import product
def input():
    return sys.stdin.readline()[:-1]

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

def main():
    N = int(input())

    arr = factorization(N)
    l = []
    for i in arr:
        for j in range(i[1]):
            l.append(i[0])

    A = 10**13
    B = 10**13
    for i in product([0, 1], repeat=len(l)):
        a = 1
        b = 1
        for k in range(len(l)):
            if i[k] == 0:
                a *= l[k]
            if i[k] == 1:
                b *= l[k]
        if a + b < A + B:
            A = a
            B = b
    print(A + B - 2)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

def main():
    N = int(input())

    ans = 1e18
    for i in range(1, N + 1):
        if i * i > N:
            break
        if N % i != 0:
            continue
        j = N // i
        ans = min(ans, i + j - 2)
    print(ans)


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

def checker(x):
    for i in range(2,x//2+1):
        if x % i == 0:
            return False
    return True

cnt = 0
q = int(input())
for _ in range(q):
    v=int(input())
    if checker(v):
        cnt += 1
print(cnt)

### FIXED CODE ###

def checker(x):
    if x == 2:
        return True
    if x < 2 or x % 2 == 0 :
        return False
    for i in range(2,int(x**0.5)+1):
        if x % i == 0 :
            return False
    return True

cnt=0
q=int(input())
for _ in range(q):
    v=int(input())
    if checker(v):
        cnt += 1
print(cnt)
### BUGGY CODE ###

h,n = map(int, input().split())

INF = 1e100

dp = [[INF] * (10 ** 4 + 1) for i in range(10 ** 3 + 1)]

dp[0][0] = 0

for i in range(n):
    a, b = map(int, input().split())
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j] , dp[i][j])
        dp[i+1][min(h, (j+a))] = min(dp[i+1][min(h, (j+a))], dp[i+1][j] + b)

print(dp[n][h])

### FIXED CODE ###

h,n = map(int, input().split())

INF = 1e100

dp = [[INF] * (10 ** 4 + 1) for i in range(10 ** 3 + 1)]

dp[0][0] = 0

for i in range(n):
    a, b = map(int, input().split())
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j] , dp[i][j])
        dp[i+1][min(h, (j+a))] = min(dp[i+1][min(h, (j+a))], dp[i+1][j] + b)

print(dp[n][h])
### BUGGY CODE ###

N, K = map(int, input().split())
footing = list(map(int, input().split()))


dp = [10 ** 10] * N
dp[0] = 0

# give
'''
for i in range(N-1):
    if dp[i+1] > dp[i] + abs(footing[i+1] - footing[i]):
        dp[i+1] = dp[i] + abs(footing[i+1] - footing[i])

    if i < N-2:
        if dp[i+2] > dp[i] + abs(footing[i+2] - footing[i]):
            dp[i+2] = dp[i] + abs(footing[i+2] - footing[i])

print(dp[N-1])
'''
# get

for i in range(1,N):
    if dp[i] > dp[i-1] + abs(footing[i]-footing[i-1]):
        dp[i] = dp[i-1] + abs(footing[i]-footing[i-1]) 

    for j in range(2,K+1): 
        if i >= j:
            if dp[i] > dp[i-j] + abs(footing[i]-footing[i-j]):
                dp[i] = dp[i-j] + abs(footing[i]-footing[i-j]) 

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
footing = list(map(int, input().split()))


dp = [10 ** 10] * N
dp = dp + [10 ** 10] * 1000
dp[0] = 0

footing = footing + [0] * 1000
# give
'''
for i in range(N-1):
    for k in range(1, K+1):
        if dp[i+k] > dp[i] + abs(footing[i+k] - footing[i]):
            dp[i+k] = dp[i] + abs(footing[i+k] - footing[i])

print(dp[N-1])
'''
# get
for i in range(1,N):
    for j in range(1,min(K+1, i+1)): 
        dp[i] = min(dp[i],dp[i-j] + abs(footing[i]-footing[i-j])) 

print(dp[N-1])
### BUGGY CODE ###

import math
f=0
n=int(input())
a=list(map(int,input().split()))
p = [0]*10**6
for i in range(0, len(a)):
    for j in range(2, int(math.sqrt(a[i]))+1):
        if a[i] % j == 0:
            p[j] += 1
    if max(p)>1:
        f=1
        break
if f==0:
    print("pairwise coprime")
else:
    _gcd=a[0]
    for i  in range(1,len(a)):
        _gcd=math.gcd(_gcd,a[i])
    if _gcd==1:
        print("setwise coprime")
    else:
        print("not coprime")
    

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
M = max(a)+1
if M == 2:
    print("pairwise coprime")
    exit()
count = [0]*(M)
prime = [2,3,5,7,11,13]
for i in range(14,int(M**0.5)+2):
    check = True
    for j in prime:
        if i%j == 0:
            check = False
            break
    if check:
        prime.append(i)
 
for i in a:
    for j in prime:
        if i < j:
            break
        if i%j==0:
            while i%j == 0:
                i //= j
            count[j] += 1
    if i > 1:
        count[i] += 1
 
ans = max(count)
 
if ans == 1:
    print("pairwise coprime")
elif ans == n:
    print("not coprime")
else:
    print("setwise coprime")
### BUGGY CODE ###

ls = []
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    if i%2==0:
        ls = [a[i]]+ls
    else:
        ls.append(a[i])
if n%2 == 0:
    print(*reversed(ls))
else:
    print(*ls)

### FIXED CODE ###

from collections import deque
ls = deque()
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    if i%2==0:
        ls.appendleft(a[i])
    else:
        ls.append(a[i])
if n%2 == 0:
    print(*reversed(ls))
else:
    print(*ls)
### BUGGY CODE ###

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

import sys

input = sys.stdin.readline

def main():
    N = int(input())
    S = list(map(int, input().split()))
    odd = {}
    even = {}
    for i in range(N):
        if i % 2 == 0:
            if S[i] not in even:
                even[S[i]] = 1
            else:
                even[S[i]] += 1
        else:
            if S[i] not in odd:
                odd[S[i]] = 1
            else:
                odd[S[i]] += 1

    n = 1000000000
    even_max1 = 0
    even_max2 = 0
    odd_max1 = 0
    odd_max2 = 0
    for ek, ev in even.items():
        if ev > even_max1:
            even_max1 = ev
        elif ev > even_max2:
            even_max2 = ev

    for ok, ov in odd.items():
        if ov > odd_max1:
            odd_max1 = ov
        elif ov > odd_max2:
            odd_max2 = ov

    for ek, ev in even.items():
        if ev < even_max2:
            continue
        for ok, ov in odd.items():
            if ov < odd_max2:
                continue
            if ek == ok:
                n = min(n, N - max(even[ek], odd[ok]))
            else:
                n = min(n, N - even[ek] - odd[ok])
    print(n)

main()


### FIXED CODE ###

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

import sys

input = sys.stdin.readline

def main():
    N = int(input())
    S = list(map(int, input().split()))
    odd = {}
    even = {}
    for i in range(N):
        if i % 2 == 0:
            if S[i] not in even:
                even[S[i]] = 1
            else:
                even[S[i]] += 1
        else:
            if S[i] not in odd:
                odd[S[i]] = 1
            else:
                odd[S[i]] += 1

    n = 1000000000
    emk = None
    ev1 = None
    ev2 = 0
    for ek, ev in even.items():
        if emk is None:
            emk = ek
            ev1 = ev
        elif ev > ev1:
            emk = ek
            ev2 = ev1
            ev1 = ev
        elif ev > ev2:
            ev2 = ev

    omk = None
    ov1 = None
    ov2 = 0
    for ok, ov in odd.items():
        if omk is None:
            omk = ok
            ov1 = ov
        elif ov > ov1:
            omk = ok
            ov2 = ov1
            ov1 = ov
        elif ov > ov2:
            ov2 = ov

    if emk != omk:
        n = min(n, N - ev1 - ov1)
    else:
        n = min(n, N - ev1 - ov2, N - ev2 - ov1)

    print(n)

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

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

    ans = 0
    if not 10 % P == 0:
        d = [0] * (P+1)
        s = 0

        d[0] = 1
        for i in range(N):
            s += int(S[N-i-1]) * 10**i % P
            s %= P
            d[s] += 1

        for m in range(P):
            if d[m] > 0:
                ans += d[m] * (d[m]-1) // 2

    else:
        for i in range(N):
            if int(S[i]) % P == 0:
                ans += i+1



    print(ans)


if __name__ == "__main__":
  main()


### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**9)


INF=10**20
def solve(N,P,S,fact):
    ans = 0

    if not 10 % P == 0:
        d = [0] * (P+1)
        s = 0
 
        d[0] = 1
        for i in range(N):
            s += S[N-i-1] * fact[i]
            s %= P
            # s = int(s)
            d[s] += 1
            # print(s)
 
        for m in range(P):
            if d[m] > 0:
                ans += d[m] * (d[m]-1) // 2
 
    else:
        for i in range(N):
            if S[i] % P == 0:
                ans += i+1

 
    return ans

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = list(next(tokens))  # type: str

    fact = [pow(10,i,P) for i in range(N)]

    S = list(map(int,S))
    S = np.array(S)
    print(solve(N, P, S,np.array(fact)))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('solve', '(i8,i8,i8[:],i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()