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

class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))

query = []

for i in range(Q):
    l, r, = map(int, input().split())
    query.append((l - 1, r, i))

query.sort(key = lambda x: x[1])

rt = 0
L = [None for _ in range(N)]
res = [0 for _ in range(Q)]
bit = BinaryIndexedTree(N)

for l, r, id in query:
    while rt < r:
        if L[C[rt]] is not None:
            bit.add(L[C[rt]] + 1, -1)
        L[C[rt]] = rt
        bit.add(rt + 1, 1)
        rt += 1
    res[id] = bit.sum(r) - bit.sum(l)

print('\n'.join(map(str, res)))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))

query = []

for i in range(Q):
    l, r, = map(int, input().split())
    query.append((l - 1, r, i))

query.sort(key = lambda x: x[1])

rt = 0
L = [None for _ in range(N)]
res = [0 for _ in range(Q)]
bit = [0 for _ in range(N + 1)]

for l, r, id in query:
    while rt < r:
        if L[C[rt]] is not None:
            idx = L[C[rt]] + 1
            while idx <= N:
                bit[idx] -= 1
                idx += idx & -idx
        L[C[rt]] = rt
        idx = rt + 1
        while idx <= N:
            bit[idx] += 1
            idx += idx & -idx
        rt += 1
    sr = 0
    sl = 0
    idx = r
    while idx:
        sr += bit[idx]
        idx -= idx & -idx
    idx = l
    while idx:
        sl += bit[idx]
        idx -= idx & -idx
    res[id] = sr - sl

print('\n'.join(map(str, res)))
### BUGGY CODE ###

import copy

def gcd( x, y ):
    while y != 0:
        x, y = y, x%y
    return x

def coprime(a, b):
    return gcd(a, b) == 1

A , B = map(int , input().split())
gcd_value = gcd(A , B)
cd = []

for i in range(1,gcd_value + 1):
    if A % i == 0 and B % i == 0:
        cd.append(i)
cnt = copy.deepcopy(cd)
i = 0
j = 1
while i < len(cnt) - 1:
#for i in range(len(cnt) - 1):
    j = i + 1
    while j < len(cnt):
    #for j in range(i + 1 , len(cnt)):
        if not coprime(cnt[i] , cnt[j]):
            if cnt[j] in cnt:
                cnt.remove(cnt[j])
                continue
        j += 1
    i += 1
#print(cnt)
print(len(cnt))


### FIXED CODE ###

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True
def gcd( x, y ):
    while y != 0:
        x, y = y, x%y
    return x

def coprime(a, b):
    return gcd(a, b) == 1

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
A , B = map(int , input().split())
#A = 100000000000
#B = 50000000000
#print(make_divisors(A))

gcd_value = gcd(A , B)
cd = []
div = make_divisors(gcd_value)

for i in range(len(div)):
    if A % div[i] == 0 and B % div[i] == 0 and is_prime(div[i]):
        cd.append(div[i])
print(len(cd) + 1)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

N, M = [int(x) for x in input().split()]
A = {}
for _ in range(N):
    x, y = [int(x) for x in input().split()]
    if x  not in A:
       A[x] = []
    A[x].append(y)

for key in A:
    A[key].sort()


total = 0
for x in range(1, M + 1):
    max = 0
    max_index = -1
    for k, v in sorted(A.items()):
        if k > x:
            break
        if v[-1] > max:
            max = v[-1]
            max_index = k
    if max_index != -1:
        total += A[max_index].pop()
        if len(A[max_index]) == 0:
            A[max_index].append(-1)


print(total)





### FIXED CODE ###

from collections import defaultdict
import heapq

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

dict = defaultdict(list)
for _ in range(N):
    A, B = [int(x) for x in input().split()]
    dict[A].append(B)

h = []
total = 0
for x in range(1, M + 1):
    for y in dict[x]:
        heapq.heappush(h, -y)
    if h:
        total += heapq.heappop(h)

print(-total)
### BUGGY CODE ###

MOD = 10**9 + 7

def modinv(a, mod = 10**9 + 7):
    return pow(a, mod - 2, mod)

def comb(n, r, mod = 10**9 + 7):
    r = min(n, n - r)
    res = 1
    for i in range(r):
        res = res * (n - i) % mod
        res = res * modinv(i + 1, mod) % mod
    return res

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

ans = pow(2, n, MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD)

print(ans)


### FIXED CODE ###

MOD = pow(10, 9) + 7

def modinv(a, mod):
    return pow(a, mod - 2, mod) % mod

def comb(n, r, mod):
    r = min(r, n - r)
    res = 1
    for i in range(r):
        res = res * (n - i) % mod
        res = res * modinv(i + 1, mod) % mod
    return res

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

ans = (pow(2, n, MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD)) % MOD

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

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


for i in range(1,n+1):
    print(str(a.index(i)+1), end=' ')
    

### FIXED CODE ###

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

ans = [0 for i in range(n)]

for i in range(n):
    ans[a[i]-1] = i+1

print(' '.join(map(str,ans)))
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n, k =map(int,input().split())
    A = list(map(int,input().split())) + [0]
    while k > 0:
        B = [0] * (n + 1) 
        for i, a in enumerate(A):
            B[max(0, i - a)] += 1
            B[min(n, i + a + 1)]  -= 1
        if B[0] == n:
            flag = True
        for i in range(1, n+1):
            B[i] += B[i-1]
            if B[i] != n and i < n:
                flag = False
        A = B[:]
        if flag:
            break
        k -= 1
    print(" ".join(map(str, B[:-1])))

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n, k =map(int,input().split())
    A = list(map(int,input().split())) + [0]
    while k > 0:
        B = [0] * (n + 1) 
        for i, a in enumerate(A):
            B[max(0, i - a)] += 1
            B[min(n, i + a + 1)]  -= 1
        if B[0] == n:
            flag = True
        for i in range(1, n+1):
            B[i] += B[i-1]
            if B[i] != n and i < n:
                flag = False
        A = B[:]
        if flag:
            break
        k -= 1
    print(" ".join(map(str, B[:-1])))

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

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    A, B, C = map(int, input().split())
    ans = INF
    for a1 in range(1, A):
        a2 = A - a1
        ans = min(ans, abs(a1 * B * C - a2 * B * C))
    for b1 in range(1, B):
        b2 = B - b1
        ans = min(ans, abs(A * b1 * C - A * b2 * C))
    for c1 in range(1, C):
        c2 = C - c1
        ans = min(ans, abs(A * B * c1 - A * B * c2))

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


def main():
    A, B, C = map(int, input().split())

    ans = INF
    if A % 2 == 0 or B % 2 == 0 or C % 2 == 0:
        ans = 0

    ans = min(ans, B * C)
    ans = min(ans, A * C)
    ans = min(ans, A * B)

    print(ans)


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

#b問題
n=int(input())
ans=1
a=list(int(y) for y in input().split())
# print(a)
for i in range(n):
    ans=ans*a[i]
    if ans>10**18:
        ans=-1
print(ans)

### FIXED CODE ###

#b問題
n=int(input())
ans=1
a=list(int(y) for y in input().split())
# print(a)
if 0 in a:
    print(0)
else:
    for i in range(n):
        ans*=a[i]
        if ans>10**18:
            ans=-1
            break
    print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i] != s[j]:
            for k in range(j+1,n):
                if s[k] not in (s[i],s[j]) and j-i != k-j:
                    cnt +=1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = s.count('R')*s.count('G')*s.count('B')
for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i] != s[j]:
            if 2*j-i > n-1:
                break
            if s[2*j-i] not in(s[i],s[j]):
                cnt -= 1
print(cnt)
### BUGGY CODE ###

import functools
import copy

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

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

if N == 2:
    n = max(A)
else:
    for i in range(N):
        l = copy.copy(A)
        l.pop(i)
        res = functools.reduce(lambda x, y: gcd(x, y), l)
        if res > n:
            n = res
print(n)


### FIXED CODE ###

import functools
import copy

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

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

l = [0] * N  #L_i, i = 0, 1, 2, ..., N-1
for i in range(N):
    if i == 0:
        continue
    else:
        l[i] = gcd(l[i-1], A[i-1])

r = [0] * N #R_i, i = 0, 1, 2, ..., N-1
for j in range(N):
    if j == 0:
        continue
    else:
        r[N-j-1] = gcd(r[N-j], A[N-j])

m = [0] * N
for i in range(N):
    m[i] = gcd(l[i], r[i])

print(max(m))
### BUGGY CODE ###

# （高速化）貰うDP
# mainで囲まないと間に合わない
def main():
    N,K=map(int,input().split())
    H=list(map(int,input().split()))
    INF=10**9
    add_list=[INF]*K

    H.extend(add_list)

    dp=[INF]*(N+100) #Kの分追加
    dp[0]=0
    for n in range(N):
        for k in range(n+1,n+K+1):
            dp[k]=min(dp[k], dp[n]+abs(H[n]-H[k]))
    print(dp[N-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

# 貰うDP
N,K=map(int,input().split())
h=list(map(int,input().split()))
INF=10**9
dp=[INF]*(N)
dp[0]=0

for n in range(1,N):
    dp[n]=min([dp[k] + abs(h[n] - h[k]) for k in range(max(0,n-K), n)])
print(dp[N-1])
### BUGGY CODE ###

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

for i in range(M):
  L, R = map(int, input().split())
  pass_card = [i for i in range(L, R+1)]
  if  i == 0:
    ans = pass_card
  elif i > 0:
    ans = list(set(ans) & set(pass_card))

print(len(ans))

### FIXED CODE ###

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

L_list = []
R_list = []
for i in range(M):
  L, R = map(int, input().split())
  L_list.append(L)
  R_list.append(R)

L = max(L_list)
R = min(R_list)

if R < L:
  print(0)
else:
  print(R - L + 1)
### BUGGY CODE ###

from collections import deque
import math


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]

    d = deque()
    d.append([Ch - 1, Cw - 1])

    cost = [[math.inf for _ in range(W)] for _ in range(H)]
    cost[Ch - 1][Cw - 1] = 0

    while d:
        r, c = d.popleft()

        for dr, dc in [[-1, 0], [1, 0], [0, -1], [0, 1]]:  # 上下左右
            nr = r + dr
            nc = c + dc
            if 0 <= nr < H and 0 <= nc < W and S[nr][nc] == "." and cost[nr][nc] > cost[r][c]:
                cost[nr][nc] = cost[r][c]
                d.appendleft([nr, nc])

        for dr in range(-2, 3, 1):  # ワープ
            for dc in range(-2, 3, 1):
                if dr == 0 and dc == 0:
                    continue
                nr = r + dr
                nc = c + dc
                if 0 <= nr < H and 0 <= nc < W and S[nr][nc] == "." and cost[nr][nc] > cost[r][c]:
                    cost[nr][nc] = cost[r][c] + 1
                    d.append([nr, nc])

    if cost[Dh - 1][Dw - 1] == math.inf:
        ans = -1
    else:
        ans = cost[Dh - 1][Dw - 1]

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [input() for _ in range(H)]

    Q = deque([[Ch - 1, Cw - 1, 0]])  # 座標とワープ回数

    cost = [[-1 for _ in range(W)] for _ in range(H)]  # ワープ回数を記録

    while Q:
        r, c, cnt = Q.popleft()

        if cost[r][c] != -1:  # 訪れたことがある
            continue

        cost[r][c] = cnt

        for dr in range(-2, 3):
            for dc in range(-2, 3):
                nr = r + dr
                nc = c + dc

                if 0 <= nr < H and 0 <= nc < W and S[nr][nc] == ".":
                    if abs(dr) + abs(dc) == 1:  # 上下左右
                        Q.appendleft([nr, nc, cnt])
                    elif abs(dr) + abs(dc) >= 2:  # ワープ
                        Q.append([nr, nc, cnt + 1])

    print(cost[Dh - 1][Dw - 1])


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

n,k = map(int,input().split())	
li = tuple(map(int,input().split()))
dp = [0] + [float("inf")]*(n-1)
for i in range(1,n):
    for j in range(max(0, i-k),i):
        dp[i] = min(dp[i], dp[j] + abs(li[i] - li[j]))
print(dp[-1])


### FIXED CODE ###

n,k = map(int,input().split())	
li = tuple(map(int,input().split()))
dp = [0] + [float("inf")]*(n-1)
for i in range(1,n):
    for j in range(max(0, i-k),i):
        dp[i] = min(dp[i], dp[j] + abs(li[i] - li[j]))
print(dp[-1])
### BUGGY CODE ###

import math

def prime(m):
    pf = {}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    return pf

def calc_tmpans(primes, tmpans, cnt, val):
    if len(primes) == 0:
        tmpans[val] = cnt
    else:
        (p, v) = primes[0]
        for i in range(v + 1):
            calc_tmpans(primes[1:], tmpans, cnt * (i + 1), val * (p ** i) )

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

    tmpans = [0]*(N+1)
    ans = 0
    for c in reversed(range(1, N)):
        if tmpans[N - c] != 0:
            ans += tmpans[N-c]
        else:
            p = prime(N - c)
            tmp = 1
            p_list = list(p.items())
            # for (k, v) in p_list:
            #     tmp *= (v + 1)
            calc_tmpans(p_list, tmpans, 1, 1)
            ans += tmp
    return sum(tmpans)

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

### FIXED CODE ###

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data
 
p_list = get_sieve_of_eratosthenes(10**3)
 
def factorization_counta(n):
    arr = []
    temp = n
    for i in p_list:
        if i * i > n:
            break
        elif temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append(cnt)
            
    if temp != 1:
        arr.append(1)
    if arr == []:
        arr.append(1)
    return arr

def main():
    N = int(input())
    ans = 1
    for c in range(2, N):
        p = factorization_counta(c)
        tmp = 1
        for v in p:
            tmp *= (v + 1)
        ans += tmp
    return ans
 
if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

hisi=0
tyou=0
while True:
    try:
        a,b,c=map(int,input().split(","))
        if a**2+b**2==c**2:
            tyou +=1
        elif a==b:
            hisi +=1
    except:
        print(tyou)
        print(hisi)


### FIXED CODE ###

hisi=0
tyou=0
while True:
    try:
        a,b,c=map(int,input().split(","))
        if a**2+b**2==c**2:
            tyou +=1
        elif a==b:
            hisi +=1
    except:
        print(tyou)
        print(hisi)
        break
### BUGGY CODE ###

社員数 = int(input())

上司 = list(map(int, input().split(' ')))

for 社員番号 in range(1, 社員数+1):
    print(上司.count(社員番号))


### FIXED CODE ###

num_employee = int(input())
num_subordinate = [0] * num_employee

for boss in map(int, input().split(' ')):
    num_subordinate[boss-1] += 1

print('\n'.join(map(str, num_subordinate)))
### BUGGY CODE ###


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

n = -1
for i in range(1,N+1):
    try:
        n = a.index(i)
    except:
        i = i-1
        break
    a = a[n:]

if n > -1:
    M = N - i
else:
    M = -1

print(M)



### FIXED CODE ###


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

t = 1
for x in a:
    if x == t:
        t += 1
t -= 1

if t == 0:
    print(-1)
else:
    print(N-t)
### BUGGY CODE ###

import numpy as np
from numba import njit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A)

fin = np.array([N] * N)


@njit(cache=True)
def calc_b(a):
    b = np.array([0] * N)
    for i in range(N):
        if a[i] == N:
            b[i] = a[i]
        else:
            l = max(0, i - a[i])
            r = min(N - 1, i + a[i])

            for j in range(l, r + 1):
                b[j] += 1
    return b


for k in range(K):
    a = calc_b(a)

    if all(a == fin):
        break

a = [str(_) for _ in a]
print(' '.join(a))


### FIXED CODE ###

import numpy as np
from numba import njit

N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
a = np.array(A, dtype=int)


fin = [N] * N

@njit(cache=True)
def calc_b(a):
    b = np.zeros(N, dtype=np.int64)
    for i, _a in enumerate(a):
        l = max(0, i - _a)
        r = min(N - 1, i + _a)

        # imos hou
        b[l] += 1
        if r + 1 < N:
            b[r + 1] -= 1

    b = np.cumsum(b)
    # print('b_sum', b)
    return b


for k in range(min(K,100)):
    # print('a', a)
    a = calc_b(a)
    # if all(a == fin):
    #     break

a = [str(_) for _ in a]
print(' '.join(a))
# print('step=', k)
### BUGGY CODE ###

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

amari = []

for i in range(0, 10000000):
    if a * i % b == c:
        print("YES")

    else:
        if a % b not in amari:
            amari.append(a % b)
        else:
            print("NO")



### FIXED CODE ###

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

amari = []

for i in range(0, 10000000):
    d = a * i
    if d % b == c:
        print("YES")
        break

    else:
        if d % b not in amari:
            amari.append(d % b)
        else:
            print("NO")
            break
### BUGGY CODE ###

import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

#実際に書き込む
N = ri()
S = [rs() for _ in range(N)]
answer = 0
for a in range(N):
    for b in range(N):
        bool = True
        for i in range(N):
            for j in range(i+1, N):
                y1 = (i+a)%(N)
                x1 = (j+b)%(N)
                y2 = (j+a)%(N)
                x2 = (i+b)%(N)
                
                if S[y1][x1] != S[y2][x2]:
                    
                    bool = False
                    break
            else:
                continue
            break
        else:
            if bool:
                #print(a, b, i, j, y1, x1, y2, x2)
                answer += 1
print(answer)

#16



### FIXED CODE ###

import sys
import numpy as np

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip() # ignore trailing spaces

N = ri()
S = np.array([list(rs()) for _ in range(N)])

S = np.concatenate([S, S], axis=0)
answer = 0
for b in range(N):
    S2 = S[b:b+N]
    if (S2 == S2.T).all():
        answer += N

print(answer)
### BUGGY CODE ###

import sys

h,w=[int(x) for x in input().rstrip().split()]
l=[]
black=0
for i in range(h):
  s=[x for x in input()]
  l.append(s)

black+=sum(map(lambda x:x.count('#'),l))

dist=[[False]*w for i in range(h)]


def bfs():
  cnt=1
  stack=[[0,0,cnt]]

  while(stack):
    x,y,cnt=stack.pop(0)
    dist[y][x]=True
    
    move=[[x+1,y],[x-1,y],[x,y+1],[x,y-1]]

    for mx,my in move:
      if not(0<=my<=h-1) or not(0<=mx<=w-1) or l[my][mx]=="#" or dist[my][mx]==True:
        continue

      
      stack.append([mx,my,cnt+1])
    
      if my==h-1 and mx==w-1:
        print(h*w-cnt-black-1)
        sys.exit()
  print(-1)

if __name__=="__main__":
  bfs()

### FIXED CODE ###

import sys
 
h,w=[int(x) for x in input().rstrip().split()]
l=[]
black=0
for i in range(h):
  s=[x for x in input()]
  l.append(s)
  black+=sum(j.count("#") for j in s)
 
done=[[float('inf')]*w for i in range(h)]
def bfs():
  stack=[[0,0]]
  done[0][0]=0
  while(stack):
    x,y=stack.pop(0)
    move=[[x+1,y],[x-1,y],[x,y+1],[x,y-1]]
 
    for mx,my in move:
      if not(0<=my<=h-1) or not(0<=mx<=w-1) or l[my][mx]=="#" or done[my][mx]!=float('inf'):
        continue

      done[my][mx]=done[y][x]+1
      stack.append([mx,my])
      
      if my==h-1 and mx==w-1:
        print(h*w-done[my][mx]-black-1)
        sys.exit()
  print(-1)
 
if __name__=="__main__":
  bfs()
### BUGGY CODE ###

n = int(input())
s = input()
res=0
for i in range(1000):
    digits=str(i)
    if i<100:
        digits='0'*(3-len(str(i)))+digits
        #print(digits)
    cnt = 0
    for j in s:
        if j==digits[cnt]:
            #print(digits)
            cnt+=1
        if cnt>=3:
            res+=1
            break
print(res)

### FIXED CODE ###

n = int(input())
s = input()
res=0
for i in range(1000):
    digits=str(i)
    if i<100:
        digits='0'*(3-len(str(i)))+digits
        #print(digits)
    cnt = 0
    for j in s:
        if j==digits[cnt]:
            #print(digits)
            cnt+=1
        if cnt>=3:
            res+=1
            break
print(res)
### BUGGY CODE ###

import itertools

A, B, C, K = map(int, input().split(" "))
data = [1 for _ in range(A)] + [0 for _ in range(B)] + [-1 for _ in range(C)]

conbs = list(itertools.combinations(data, K))
max_val = 0
for conb in conbs:
    if sum(conb) > max_val:
        max_val = sum(conb)
print(max_val)


### FIXED CODE ###

A, B, C, K = map(int, input().split(" "))
if K-A <= 0:
    print(K)
else:
    if K - (A + B) <= 0:
        print(A)
    elif K == A+B+C:
        print(A-C)
    else:
        print(A - (K-(A+B)))
### BUGGY CODE ###

s=input()
n=len(s)
k=int(input())
da=[]
for i in range(1,n+1):
    for j in range(i):
        da.append(s[j:i])
da=list(set(da))
da=sorted(da)
print(da[k-1])

### FIXED CODE ###

s=input()
n=len(s)
k=int(input())
da=[]
for i in range(0,n):
    for j in range(5):
        if i+j<n+1:
            da.append(s[i:i+j+1])
da=list(set(da))
da=sorted(da)
print(da[k-1])
### BUGGY CODE ###

N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
A.sort()
sumcost = 0
k = 0
for i in range(M):
    if M-k>A[0][1]:
        sumcost += A[0][0]*A[0][1]
        k += A[0][1]
        A.pop(0)
    else:
        sumcost += A[0][0]*(M-k)
        break

print(sumcost)

### FIXED CODE ###

N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
A.sort()
sumcost = 0
for i in range(M):
    sumcost += A[0][0]
    A[0][1] -= 1
    if A[0][1] < 1:
        A.pop(0)

print(sumcost)