Harryxun/stf_run huggingface dataset:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

com_mx=200005
mod=998244353
fac=[0]*com_mx
finv=[0]*com_mx
inv=[0]*com_mx
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,com_mx):
  fac[i]=fac[i-1]*i%mod
  inv[i]=mod-inv[mod%i]*(mod//i)%mod
  finv[i]=finv[i-1]*inv[i]%mod

def com(n,k):
  if n<k or n<0 or k<0:
    return 0
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod

n,m,k=LI()
ans=0
col=m
for x in range(n)[::-1]:
  now=col
  now*=com(n-1,x)
  if x<=k:
    ans+=now
    ans%=mod
  col*=m-1
print(ans)

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

com_mx=200005
mod=998244353
fac=[0]*com_mx
finv=[0]*com_mx
inv=[0]*com_mx
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,com_mx):
  fac[i]=fac[i-1]*i%mod
  inv[i]=-inv[mod%i]*(mod//i)%mod
  finv[i]=finv[i-1]*inv[i]%mod

def com(n,k):
  if n<k or n<0 or k<0:
    return 0
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod

def main():
  n,m,k=LI()
  res=0
  tmp=m*pow(m-1,n-k-1,mod)
   
  for r in range(n-k-1,n):
    res=(res+tmp*com(n-1,r)%mod)%mod
    tmp=tmp*(m-1)%mod
  return res

# main()
print(main())
N, M = map(int, input().split())
A = []
import sys
flg = 0
for i in range(M):
    a = int(input())
    if a == 1 or a == 2:
        flg = a
    if i != 0:
        if a == A[-1] + 1:
            print(0)
            sys.exit()
    A.append(a)
def step(n):
    steps = [0 for i in range(n + 1)]
    if flg == 0:
        steps[1] = 1
        steps[2] = 2
    elif flg == 1:
        steps[2] = 1
    else:
        steps[1] = 1
    for i in range(3, n + 1):
        steps[i] = steps[i - 1] + steps[i - 2]
        if i in A:
            steps[i] = 0
    return steps[n] % 1000000007
print(step(N))

### FIXED CODE ###

N, M = map(int, input().split())
A = []
for i in range(M):
    a = int(input())
    A.append(a)
def step(n):
    steps = [0 for i in range(n + 1)]
    ind = 0
    steps[0] = 1
    steps[1] = 1
    if M != 0:
        if 1 == A[ind]:
            steps[1] = 0
            if ind < M-1:
                ind += 1
    for i in range(2, n + 1):
        steps[i] = steps[i - 1] + steps[i - 2]
        if M != 0:
            if i == A[ind]:
                steps[i] = 0
                if ind < M-1:
                    ind += 1
    return steps[n] % 1000000007
print(step(N))
n,d = int(input())
ans = 0
for i in range(n):
  x,y = map(int,input().split())
  if(d>=(x**2+y**2)**(1/2)):
    ans += 1
print(ans)

### FIXED CODE ###

n,d = map(int,input().split())
ans = 0
for i in range(n):
  x,y = map(int,input().split())
  if(d >= (x**2+y**2)**(1/2)):
    ans += 1
print(ans)
from collections import Counter
from itertools import accumulate
from functools import reduce

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

c = Counter([0] + [x % M for x in accumulate(A)])
ans = reduce(add, [v*(v-1)//2 for v in c.values()])
print(ans)


### FIXED CODE ###

from collections import Counter
c = Counter()

N, M = map(int,input().split())
a = list(map(int,input().split())) 
s = 0
c[s] += 1
for i in range(N):
  s = (s + a[i]) % M
  c[s] += 1
# print(c)
S=0
# t=0
for (i,k) in c.items():
  if k > 1:
    S += (k-1)*k//2
  # t += k
print(S)
# print(t)
n = int(input())
a = np.array(list(map(int,input().split())))

count = 0
while 1:
    count+1
    a=a/2
print(count)


### FIXED CODE ###

count= -1
flag = 1

num_list = [0]*int(input())
num_list = [int(x) for x in input().split()]

while 1:
    i=0
    for x in num_list:
        if x%2==1:
            flag = 0
            break
        else:
            num_list[i]=num_list[i]/2
        i=i+1
    count = count + 1
    if flag==0:
        break


print(count)
n = input()
a = []
a = [input for i in range(n)]
i = 0
j = 1
max = a[j]-a[i]
while n > i:
   j = i+1
   while n > j:
        if max < a[j]-a[i]:
           max = a[j]-a[i]
        j+=1
    i+=1

print max

### FIXED CODE ###

N = int(raw_input())
min = int(raw_input())
max = int(raw_input())

ans = max - min
if max < min:
    min = max
 
for i in range(N - 2):
    R = int(raw_input())
    if R - min > ans:
        ans = R - min
    if R < min:
        min = R
 
print ans
while True:
	n, r = map(int, input().split())
	if (n, r) == (0, 0):
		break
	cards = list(range(1, n+1))[::-1]
	print(cards)

	for i in range(r):
		p, c = map(int, input().split())
		cards = cards[p-1:p-1+c] + cards[:p-1] + cards[p-1+c:]
	print(cards[0])

### FIXED CODE ###


while True:
	n, r = map(int, input().split())
	if (n, r) == (0, 0):
		break
	cards = list(range(1, n+1))[::-1]

	for i in range(r):
		p, c = map(int, input().split())
		cards = cards[p-1:p-1+c] + cards[:p-1] + cards[p-1+c:]
	print(cards[0])
list1=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
a = int(input())
print(list1[a+1])

### FIXED CODE ###

list1=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
a = int(input())
print(list1[a-1])
n=int(input())
m=int(n**0.5)+1
con_num=0
for i in range(m):
  if n%i==0:
    con_num+=1
if con_num==8 and n%2==1:
  print("1")
else:
  print("0")

### FIXED CODE ###

def I(): return int(input())
n = I()
ans = 0
if n>=105:
    for i in range(105,n+1,2):
        cnt=0
        for j in range(1,int(i**0.5)+1):
            if i % j ==0:
                if j*j==i:
                    cnt+=1
                else:
                    cnt+=2
        if cnt==8:
            ans+=1
print(ans)
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;

long long int N, K;
long long int a, b;


int main(){
    cin >> N >> K;
    vector<pair<long long int, long long int> > pairs(N);

    for(int i = 0; i < N; i++){
        cin >> a >> b;
        pairs[i] = make_pair(a, b);
    }
    sort(pairs.begin(), pairs.end());

    for(int i = 0; i < N; i++){
        K -= pairs[i].second;
        if(K <= 0){
            cout << (pairs[i].first);
            return 0;
        }
    }
    return 0;
}

### FIXED CODE ###

AB = []
N, K = map(int, input().split())

for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

AB.sort()
for ab in AB:
    K -= ab[1]
    if K <= 0:
        print(ab[0])
        exit()
N, M = map(int, input().split())
for _ in range(M):
    a, b = map(int, input().split())
    
for i in range(1, M, 1):
  a.count(i)
  b.count(i)
  
  
c = a + b

C = np.zeros((len(c), 1), dtype = 'int')

for i in range(len(C)):
  C[i,0] = c[i]
  
print(C)

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
c = []
for _ in range(M):
    a, b= map(int, input().split())
    c.append(a)
    c.append(b)
for i in range(N):
    print(c.count(i+1))
N = 10**6

N1 = [i for i in range(N+40)]
N2 = [i for i in range(N+40)]

#N1[0] = 0
#N2[0] = 0

p = [n*(n+1)*(n+2)//6 for n in range(1,200) if n *(n+1)*(n+2)//6< N+1]
p2 = [n*(n+1)*(n+2)//6 for n in range(1,200) if n *(n+1)*(n+2)//6< N+1 and n *(n+1)*(n+2)//6 % 2 ==1 ]
#print(p2)
for p_ in p:
    if p_ > N +1:
        continue
    n = min(p_*5,10**6)
    for j in range(p_,n):
#        print(j)
        if N1[j] > N1[j-p_] +1:
            N1[j] = N1[j-p_]+1
for p_ in p2:
    if p_ > N +1 :
        continue
    for j in range(p_,N +1):
        if N2[j] > N2[j-p_]+1:
            N2[j] = N2[j -p_]+1
print('a')
while True:
    n = int(input())
    if n == 0:
        break
    print(N1[n],N2[n])



### FIXED CODE ###

import copy

item = [i *(i +1) * (i+2) //6 for i in range(1,181)]
q = []
while True:
    in_ = int(input())
    if in_ == 0:
        break
    q.append(in_)

INIT = 1000
MAX = max(q) +10
ans = [INIT] *MAX
ans[0] = 0
odd_item = [i for i in item if i % 2 ==0 ]
even_item = [i for i in item if not(i % 2 == 0)]

for i in even_item:
    for j in range(0,MAX-i):
        if ans[j+i] > ans[j] + 1:
            ans[j+i] = ans[j] + 1

ans_ = copy.deepcopy(ans)

for i in odd_item:
    for j in range(0,MAX-i):
        if ans[j+i] > ans[j] + 1:
            ans[j+i] = ans[j]+1
for i in q:
    print(ans[i],ans_[i])
from collections import deque
k=int(input())
q=deque(list(range(1, 10)))
ans,x,y=0,0,0
for i in range(k):
  ans=q.popleft()
  y=ans%10
  x=ans*10+y
  if y != 0:
    q.append(tmp-1)
  q.append(tmp)
  if y != 9:
    q.append(tmp+1)
print(ans)


### FIXED CODE ###

from collections import deque
k=int(input())
q=deque(list(range(1, 10)))
ans,x,y=0,0,0
for i in range(k):
  ans=q.popleft()
  y=ans%10
  x=ans*10+y
  if y != 0:
    q.append(x-1)
  q.append(x)
  if y != 9:
    q.append(x+1)
print(ans)
def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    # b = list(map(int, input().split()))
    b = [int(i) for i in input().split()] 
  else:
    # b = [1,2,1]
    # b = [2,2]
    # b = [1,1,1,2,2,1,2,3,2]
    b = [1,1,1,1,2,3,4,5,6,1] 
    N = len(b)
  
  if check(b,N) != True:
    print(-1)
    
def check(B,lenB):
  # if 'get_ipython' in globals(): print(B)
  if lenB == 0 :
    return True
  #for i in reversed(range(lenB)):
  for i in range(lenB-1,-1,-1):
    if B[i] == i+1:
      ans = B[i]
      del B[i]
      if check(B,lenB -1) == True:
        print(ans)
        return True
        break  
  return False

main()

### FIXED CODE ###

import sys

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    b = [int(i) for i in input().split()] 
  else:
    # b = [1,2,1]
    # b = [2,2]
    b = [1,1,1,2,2,1,2,3,2]
    N = len(b)

  ans = []
  while True:
    for i in range(N-1,-1,-1):
      if b[i] == i+1:
        ans.append(i+1)
        del b[i]
        N = N -1
        break
      if i == 0:
        print(-1)
        sys.exit()
    if N == 0:
      break

  for i in reversed(ans):
    print(i)
    
main()
s=input()
print(700+100*int(s.coount("o")))

### FIXED CODE ###

s=input()
print(700+100*int(s.count("o")))
while 1:
	n=input()
	if n==0:break
	for i in range(n):
		m,e,j=map(int, raw_input().split())
		a=sum(m,e,j)
		if 100 in [m,e,j] or m+e>=180 or a>=240:print "A"
		elif a>=210 or (a>=150 and max(m,e)>=80):print "B"
		else:print"C"

### FIXED CODE ###

while 1:
	n=input()
	if n==0:break
	for i in range(n):
		m,e,j=map(int, raw_input().split())
		a=m+e+j
		if 100 in [m,e,j] or m+e>179 or a>239:print"A"
		elif a>209 or (a>149 and max(m,e)>79):print"B"
		else:print"C"
# -*- coding: utf-8 -*-

import numpy as np

# TESTCASE #
test = ""
#test = \
"""
3 2
5 1 4
2 3
1 5
ans:
14
"""

"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
ans:
338
"""

"""
3 2
100 100 100
3 99
3 99
ans:
300
"""

"""
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
ans:
10000000001
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
### MAIN ###
        
n, m = map(int, input2().split())
a = np.array(list(map(int, input2().split())), dtype="int64")
bcs = [tuple(map(int, input2().split()))[::-1] for _ in range(m)]

a.sort()
bcs = sorted(bcs, reverse=True)

i = 0
for query in bcs:
    #print(query)
    if a[i] < query[0]:
        a[i:i+query[1]] = np.maximum(a[i:i+query[1]], query[0])
        i += query[1]
        #print(a)
    
print(np.sum(a))
    










### FIXED CODE ###

# -*- coding: utf-8 -*-

import numpy as np

# TESTCASE #
test = ""
#test = \
"""
3 2
5 1 4
2 3
1 5
ans:
14
"""

"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
ans:
338
"""

"""
3 2
100 100 100
3 99
3 99
ans:
300
"""

"""
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
ans:
10000000001
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
### MAIN ###
        
n, m = map(int, input2().split())
a = np.array(list(map(int, input2().split())), dtype="int64")
bcs = [tuple(map(int, input2().split()))[::-1] for _ in range(m)]

a.sort()
bcs = sorted(bcs, reverse=True)

i = 0
for query in bcs:
    #print(query)
    a[i:i+query[1]] = np.maximum(a[i:i+query[1]], query[0])
    i += query[1]
    #print(a)    
print(np.sum(a))
import math
costs = [2,5,5,4,5,6,3,7,6]

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * math.inf
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>0:
        for a in A:
            arr = [a for a in A if D[n-costs[a-1]]==D[n]-1]
        a = max(arr)
        ans += str(a)
        n -= costs[a-1]
    print(ans)

main()

### FIXED CODE ###

costs = [2,5,5,4,5,6,3,7,6]

N, M = map(int, input().split())
A = list(map(int, input().split()))
neginf = -1 * 1e20
D = [neginf]*(N+1)

def dp(n_match):
    D[0] = 0
    for n in range(1,n_match+1):
        arr = [D[n-costs[a-1]] if n-costs[a-1]>=0 else neginf for a in A]
        D[n] = max(arr)+1

def main():
    dp(N)
    n = N
    ans = ''
    while n>1:
        arr = [ a for a in A if  n-costs[a-1]>=0 and D[n-costs[a-1]]==D[n]-1 ]
        if len(arr)>0:
            a = max(arr)
            ans += str(a)
            n -= costs[a-1]
        else:
            break
    print(ans)

main()
n=int(input())
A=sorted(list(map(int,input().split())))
L={}
for i in A:
    if i not in L:
        L[i]=1
    else:
        L[i]+=1
ans=[]
for j in range(A[0],A[-1]+1):
    if j in L:
        if j-1 in L:
            if j+1 in L:
                ans.append(L[j]+L[j+1]+L[j-1])
if len(A)>=3:
    print(max(ans))
else:
    if len(A)==1:
        print(1)
    else:
        if abs(A[0]-A[1])==1:
            print(2)
        else:
            print(1)


### FIXED CODE ###

n=int(input())
A=sorted(list(map(int,input().split())))
L={}
if n==1:
        print(1)
elif n==2:
    if abs(A[0]-A[1])==1:
        print(2)
    else:
        print(1)
else:
    for i in A:
        if i not in L:
            L[i]=1
        else:
            L[i]+=1
    ans=[]
    for j in range(A[0],A[-1]+1):
        if (j in L) and (j-1 in L) and (j+1 in L):
            ans.append(L[j]+L[j+1]+L[j-1])
        elif (j in L) and (j-1 in L):
            ans.append(L[j-1]+L[j])
        elif (j in L) and (j+1 in L):
            ans.append(L[j+1]+L[j])
        elif (j-1 in L) and (j+1 in L):
            ans.append(L[j+1]+L[j-1])
        elif (j in L):
            ans.append(L[j])
    print(max(ans))
x = int(input())
a = []
for i in range(80):
    a.append(i**5)

for i in range(79):
    for j in range(i+1,80):
        if a[i]-a[j]==x:
            A=i
            B=j
            break
        elif -a[i]-a[j]==x:
            A=-i
            B=j
            break
        elif -a[i]+a[j]==x:
            A=-i
            B=-j
            break
        elif a[i]+a[j]==x:
            A=i
            B=-j
            break
print('%d %d'%(A,B))


### FIXED CODE ###

x = int(input())
a = []
for i in range(1000):
    a.append(i**5)

for i in range(999):
    for j in range(i+1,1000):
        if a[i]-a[j]==x:
            A=i
            B=j
            break
        elif -a[i]-a[j]==x:
            A=-i
            B=j
            break
        elif -a[i]+a[j]==x:
            A=-i
            B=-j
            break
        elif a[i]+a[j]==x:
            A=i
            B=-j
            break
print('%d %d'%(A,B))
L, R = map(int, input().split())
if L + (673 - L % 673) <= R or L % 673 == 0:
  if L + (3 - L % 3) <= R or L % 3 == 0:
    print(0)
    sys.exit()
ans = 2019
a = L % 2019
b = R % 2019
for i in range(a, b):
  for j in range(i+1, b+1):
    ans = min(ans, i * j % 2019)
print(ans)

### FIXED CODE ###

import sys

L, R = map(int, input().split())
if L + (673 - L % 673) <= R or L % 673 == 0:
  if L + (3 - L % 3) <= R or L % 3 == 0:
    print(0)
    sys.exit()
ans = 2019
a = L % 2019
b = R % 2019
for i in range(a, b):
  for j in range(i+1, b+1):
    ans = min(ans, i * j % 2019)
print(ans)
N, A, B, C = map(int, input().split())
SN = [input() for _ in range(N)]

ABC = {'A': A, 'B': B, 'C': C}
ans = [""] * N
# print('ABC : ' + str(ABC))

# Recursiveにすることによって、途中で負の値になってもいくらでも遡ることが可能となる
def recursive_exec(i):
  # 最後まで辿り着いたらクリア
  if i == N:
    print('OK')
    print("\n".join(ans))
    quit()
  for L, R in (SN[i], reversed(SN[i])):	# ex) L, R in ('AB', 'BA')
    if ABC[L] > 0: # LでもRでもどちらでも良い
      ABC[L] -= 1
      ABC[R] += 1
      ans[i] = L

      # Next
      recursive_exec(i+1)

      # 0以下になったら戻して別の文字でやってみる (reversed(SN[i]))
      ABC[L] += 1
      ABC[R] -= 1

recursive_exec(0)
print('NG')

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

*I, = open(0).read().split()
N, A, B, C = map(int, I[:4])
S = I[4:]

Cnt = {"A": A, "B": B, "C": C}

ans = [""] * N
def dfs(i):
    if i == N:
        print("Yes")
        print("\n".join(ans))
        quit()

    for L, R in (S[i], reversed(S[i])):
        if Cnt[R] > 0:
            Cnt[L] += 1
            Cnt[R] -= 1

            ans[i] = L
            dfs(i + 1)

            Cnt[L] -= 1
            Cnt[R] += 1


dfs(0)
print("No")
R, C, K = map(int, input().split())
L = 4
items = [[0 for c in range(C)] for r in range(R)]
for k in range(K):
    r, c, v = map(int, input().split())
    items[r-1][c-1] = v
dp = [[[0 for limit in range(L)] for c in range(C)] for r in range(R)]
for r in range(R):
    for c in range(C):
        upper = 0 if r == 0 else max(dp[r-1][c])
        left = [0]*L if c == 0 else dp[r][c-1]
        item = items[r][c]
        dp[r][c][0] = max(upper, left[0])
        dp[r][c][1] = max(upper+item, left[1])
        dp[r][c][2] = max(left[1] + item, left[2])
        dp[r][c][3] = max(left[2] + item, left[3])
print(max(dp[R-1][C-1]))


### FIXED CODE ###

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

seen = []
roots = []
candidates = []

for i in range(N):
    if i+1 in seen:
        continue
    root = [i+1]
    seen.append(i+1)
    to = P[i]
    while(root[0] != to):
        root.append(to)
        seen.append(to)
        to = P[to-1]
    roots.append(root)
for root in roots:
    length = len(root)
    eachMoveBests = [None] * length
    for i in range(length):
        score = 0
        to = P[root[i]-1]
        for j in range(len(root)):
            score += C[to-1]
            to = P[to-1]
            if eachMoveBests[j] == None or score > eachMoveBests[j]:
                eachMoveBests[j] = score
    # 周回スコア
    aroundScore = eachMoveBests[len(eachMoveBests)-1]
    if length < K and aroundScore > 0:
        for i in range(len(eachMoveBests)):
            if K-i-1 % length == 0:
                candidates.append(aroundScore * ((K-i-1) // length))
            else:
                candidates.append(aroundScore * ((K-i-1) // length) + eachMoveBests[i])
    else:
        candidates.append(max(eachMoveBests[:K]))

print(max(candidates))
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def count1(nrow, k):
  keta = len(nrow)
  topmax = int(nrow[0])

  if keta == 1:
    return topmax
  ans = topmax
  ans += (keta-1)*9
  return ans

def count2(nrow, k):
  keta = len(nrow)
  topmax = int(nrow[0])

  ans = count1(nrow[1:], k)  # top==topmax
  ans += (topmax-1)*(keta-1)*9  # top!=topmax
  if keta > 2:
    ans += comb(keta-1, 2)*81
  return ans

def count3(nrow, k):
  keta = len(nrow)
  topmax = int(nrow[0])

  ans = count2(nrow[1:],k) #top==topmax
  ans += (topmax-1)*comb(keta-1,2) * 81#top!=topmax
  if keta > 3:
    ans += comb(keta-1 , 3) * 729
  return ans

nrow=input()
k = int(input())

if k==1:
  print(count1(nrow,k))
elif k == 2:
  print(count2(nrow,k))
elif k == 3:
  print(count3(nrow,k))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
#a = int(input())
# スペース区切りの整数の入力
#b, c = map(int, input().split())
# 文字列の入力
#s = input()
# 出力
#print("{} {}".format(a+b+c, s))

import numpy as np

nrow = input()
k = int(input())

l = len(nrow)

dp = np.zeros((l, 2, 4), int)
topmax = int(nrow[0])
dp[0, 0, 1] = 1  # =topmax
dp[0, 1, 0] = 1  # =0
dp[0, 1, 1] = topmax-1  # <topmax

for i in range(1, l):
  topmax = int(nrow[i])

  dp[i, 1, 0] = dp[i-1, 1, 0]  # =0
  for j in range(1,4):
    dp[i, 1, j] = dp[i-1, 1, j] + dp[i-1, 1, j-1] * 9  # =0,any

  if topmax == 0:
    for j in range(1, 4):
      dp[i, 0, j] = dp[i-1, 0, j]  #=0
  else:
    dp[i, 0, 2] = dp[i-1, 0, 1]  # =topmax,
    dp[i, 0, 3] = dp[i-1, 0, 2]  # =topmax,
    dp[i, 1, 1] += dp[i-1, 0, 1] # =0,<topmax
    dp[i, 1, 2] += dp[i-1, 0, 2]+dp[i-1, 0, 1] * (topmax-1)  # =0,<topmax
    dp[i, 1, 3] += dp[i-1, 0, 3]+dp[i-1, 0, 2] * (topmax-1)  # =0,<topmax

print(dp[l-1,0,k]+dp[l-1,1,k])
N=int(input())
import math
A=[]
for i in range(N):
  x,y=map(int, input().split())
  A.append((x,y))

def c(P1, P2, P3):
    x1, y1 = P1; x2, y2 = P2; x3, y3 = P3
    a = 2*(x1 - x2); b = 2*(y1 - y2); p = x1**2 - x2**2 + y1**2 - y2**2
    c = 2*(x1 - x3); d = 2*(y1 - y3); q = x1**2 - x3**2 + y1**2 - y3**2
    det = a*d - b*c
    x = d*p - b*q; y = a*q - c*p
    if det < 0:
        x = -x; y = -y; det = -det
    x /= det; y /= det
    r = ((x - x1)**2 + (y - y1)**2)
    return x,y,r
  
ans=(200000)**2
for i in range(N-1):
  for j in range(i+1,N):
    f=0
    x1,y1=A[i][0],A[i][1]
    x2,y2=A[j][0],A[j][1]
    x,y=(x1+x2)/2,(y1+y2)/2
    r=(x1-x)**2+(y1-y)**2
    for a,b in A:
      d=(a-x)**2+(b-y)**2
      if d>r:
        f=1
        break
    if f==0:
      ans=min(ans,math.sqrt(r))

if N>2:
  for i in range(N-2):
    for j in range(i,N-1):
      for k in range(j,N):
        f=0
        if c(A[i],A[j],A[k])!=-1:
          x,y,r=c(A[i],A[j],A[k])
          for a,b in A:
            d=(a-x)**2+(b-y)**2
            if d>r:
              f=1
              break
          if f==0:
            ans=min(ans,math.sqrt(r))

print(ans)

### FIXED CODE ###

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

def c(P1, P2, P3):
    x1, y1 = P1; x2, y2 = P2; x3, y3 = P3
    a = 2*(x1 - x2); b = 2*(y1 - y2); p = x1**2 - x2**2 + y1**2 - y2**2
    c = 2*(x1 - x3); d = 2*(y1 - y3); q = x1**2 - x3**2 + y1**2 - y3**2
    det = a*d - b*c
    x = d*p - b*q; y = a*q - c*p
    if det < 0:
        x = -x; y = -y; det = -det
    if det!=0:
      x /= det; y /= det
    r = ((x - x1)**2 + (y - y1)**2)**0.5
    return x,y,r
  
ans=(200000)**2
for i in range(N-1):
  for j in range(i+1,N):
    f=0
    x1,y1=A[i][0],A[i][1]
    x2,y2=A[j][0],A[j][1]
    x,y=(x1+x2)/2,(y1+y2)/2
    r=((x1-x)**2+(y1-y)**2)**0.5
    for a,b in A:
      d=((a-x)**2+(b-y)**2)**0.5
      if d>r:
        f=1
        break
    if f==0:
      ans=min(ans,r)
f=0

if N>2:
  for i in range(N-2):
    for j in range(i+1,N-1):
      for k in range(j+1,N):
        f=0
        x,y,r=c(A[i],A[j],A[k])
        if r>0:
          for a,b in A:
            d=((a-x)**2+(b-y)**2)**0.5
            if d>r:
              f=1
              break
          if f==0:
            ans=min(ans,r)
print(ans)
N = int(input())
A = input().split()
count = 0
for i in range(N-1):
  if A[i] > A[i+1]:
    count += A[i+1] - A[i]
    A[i+1] = A[i]

print(count)

### FIXED CODE ###

N = int(input())
A = input().split()
count = 0
for i in range(N-1):
  if int(A[i]) > int(A[i+1]):
    count += int(A[i]) - int(A[i+1])
    A[i+1] = int(A[i])

print(count)